0과 1의 쉼터

문제http://boj.ma/15886 15886번: 내 선물을 받아줘 2 boj.ma 풀이문제 요약1 * N칸에 놓인 선물을 ‘구사과’가 가져갈 때, ‘구사과’를 어디에 놓든 항상 선물을 가져가도록 하기 위한 최소 선물 개수를 구하자.아이디어‘구사과’는 어디에 놓이든 지도를 벗어나는 경우가 없으며, ‘EW’인 지역에 위치하거나 이동하게 되면 고립된다. 따라서 1 * N 칸 중 ‘EW’인 칸의 수 만큼 선물을 놓아야 한다. int cnt = 0; for (int i = 1; i 풀이 시간5분소스코드https://github.com/rogi-rogi/problem-solving/blob/main/baekjoon-online-judge/easy/15886.java problem-so..

문제https://www.codetree.ai/ko/trails/complete/curated-cards/challenge-minimum-sum-path-in-square/description 정수 사각형 최소 합 설명 | 코드트리정수 사각형 최소 합를 풀며 문제 구성과 난이도를 파악해 적절한 알고리즘을 선정해보세요. 효율적인 코드 작성을 목표로 합니다.www.codetree.ai 풀이문제 요약주어진 N*N 행렬에 대해 (1, N)에서 왼쪽/아래로만 이동하며 (N, 1)까지 도달하기 위한 최소 비용을 구하자.아이디어점화식은 다음과 같다.dp[i][j] : 현재 위치 (i, j)에 도달하기 위한 최소 비용주어진 행렬에서 (i - 1, j)와 (i, j + 1)의 비용 중 최소 비용을 골라 현재 위치 (i,..

문제https://www.codetree.ai/ko/trails/complete/curated-cards/intro-maximum-sum-path-in-square/description 정수 사각형 최대 합 설명 | 코드트리정수 사각형 최대 합를 풀며 문제 구성과 난이도를 파악해 적절한 알고리즘을 선정해보세요. 효율적인 코드 작성을 목표로 합니다.www.codetree.ai 풀이문제 요약주어진 N*N 행렬에 대해 (1, 1)에서 오른쪽/아래로만 이동하며 (N, N)까지 도달하기 위한 최대 비용을 구하자.아이디어점화식은 다음과 같다.dp[i][j] : 현재 위치 (i, j)에 도달하기 위한 최대 비용주어진 행렬에서 (i - 1, j)와 (i, j - 1)의 비용 중 최대 비용을 골라 현재 위치 (i, j)..

문제https://www.codetree.ai/ko/trails/complete/curated-cards/test-rectangle-fill-2/description 사각형 채우기 2 설명 | 코드트리사각형 채우기 2를 풀며 문제 구성과 난이도를 파악해 적절한 알고리즘을 선정해보세요. 효율적인 코드 작성을 목표로 합니다.www.codetree.ai 풀이문제 요약2 * N 크기의 사각형에 1 * 2, 2 * 1, 2 * 2 크기의 사각형으로 채우는 방법의 수를 구하자.아이디어점화식은 다음과 같다.dp[i] : 2 * i 크기 사각형을 채우는 방법의 수2 * N을 채우기 위해서는 dp[i - 1]에 2 * 1 사각형 한 개를 붙이는 경우,dp[i - 2]에 12 사각형 두 개를 붙이거나, 22 한개를 붙이는..

문제https://www.codetree.ai/ko/trails/complete/curated-cards/challenge-number-of-unique-bst/description 서로 다른 BST 개수 세기 설명 | 코드트리서로 다른 BST 개수 세기를 풀며 문제 구성과 난이도를 파악해 적절한 알고리즘을 선정해보세요. 효율적인 코드 작성을 목표로 합니다.www.codetree.ai 풀이문제 요약1 ~ N으로 이루어진 서로 다른 BST의 개수를 구하자.아이디어서로 다른 BST는 루트 노드에 따라 좌우를 구성하는 서브트리가 달라진다.1 ~ N에 대해 root가 K이면, 왼쪽 서브트리는 1 ~ K - 1, 오른쪽 서브트리는 K + 1 ~ N 노드들을 가진다.점화식은 다음과 같다.dp[i] : 노드 i개로 ..

문제https://www.codetree.ai/ko/trails/complete/curated-cards/challenge-rectangle-fill-3/description 사각형 채우기 3 설명 | 코드트리사각형 채우기 3를 풀며 문제 구성과 난이도를 파악해 적절한 알고리즘을 선정해보세요. 효율적인 코드 작성을 목표로 합니다.www.codetree.ai 풀이문제 요약2 * N 크기의 사각형에 1 * 2, 2 * 1, 1 * 1 크기의 사각형으로 채우는 방법의 수를 구하자.아이디어점화식은 다음과 같다.dp[i] : 2 * i 크기 사각형을 채우는 방법의 수1*1 사각형으로 인해 변수가 많아졌다. 하나씩 살펴보자.dp[1]은 21 한 개와, 11 두 개로 만들 수 있다.(dp[1] = 2)dp[2]는 예..

문제https://www.codetree.ai/ko/trails/complete/curated-cards/challenge-rectangle-fill/description 사각형 채우기 설명 | 코드트리사각형 채우기를 풀며 문제 구성과 난이도를 파악해 적절한 알고리즘을 선정해보세요. 효율적인 코드 작성을 목표로 합니다.www.codetree.ai 풀이문제 요약2 * N 크기의 사각형에 1 * 2, 2 * 1 크기의 사각형으로 채우는 방법의 수를 구하자.아이디어점화식은 다음과 같다.dp[i] : 2 * i 크기 사각형을 채우는 방법의 수2 * i 크기의 사각형을 채우기 위한 방법은 2 * (i - 1) 사각형에 2 * 1 사각형 하나를 붙이는 경우와, 2 * (i - 2) 사각형에 1 * 2 사각형 두개를..

문제https://www.codetree.ai/ko/trails/complete/curated-cards/challenge-climbing-stairs/description 계단 오르기 설명 | 코드트리계단 오르기를 풀며 문제 구성과 난이도를 파악해 적절한 알고리즘을 선정해보세요. 효율적인 코드 작성을 목표로 합니다.www.codetree.ai 풀이문제 요약주어진 규칙대로만 계단을 오를 수 있을 때, N층 높이의 계단을 오르는 모든 경우의 수를 구하자.아이디어점화식은 다음과 같다.dp[i] : i 번째 계단을 오르는 모든 경우의 수계단은 2칸 또는 3칸씩만 오를 수 있으므로, 현재 계단까지 오르기 위해서는 2/3칸 낮은 계단에서 올라오는 경우의 수만 존재하기 때문이다.dp[i] = 1, { N = 2 o..

문제https://www.codetree.ai/ko/trails/complete/curated-cards/intro-fibonacci-number/description 피보나치 수 설명 | 코드트리피보나치 수를 풀며 문제 구성과 난이도를 파악해 적절한 알고리즘을 선정해보세요. 효율적인 코드 작성을 목표로 합니다.www.codetree.ai 풀이문제 요약N번째 피보나치 수를 구하기 위해 DP로 점화식을 구현하자.피보나치 수열은 다음을 따른다.dp[i] = 1, N ≤ 2dp[i] = dp[i - 1] + dp[i - 2], N > 2N = int(input())# Please write your code here.def fibo(N): if N == 1 or N == 2: return 1..

문제30518번: 짜고 치는 가위바위보 (Small) 30518번: 짜고 치는 가위바위보 (Small) boj.ma 풀이문제 요약이전에 lighter가 이겼고, 현재 비기는 경우를 제외한 모든 부분 수열의 수를 구하는 문제다.아이디어부분 수열의 수를 구해야 하므로 C(N, 1) ~ C(N, N)의 모든 부분 수열 중 조건을 만족하는 경우를 찾아야 한다.조건을 만족하는 경우인지 판별해줄 judge와 private static int judge(char lighter, char smallant) { if (lighter == smallant) return 0; if ((lighter == 'R' && smallant == 'S') || (lighter..