[백준] 11726: 2 * n 타일링 - Java (DP)

목 차 문제 접근 방식 풀이 문제 접근 방식 해당 문제는 피보나치 수열 DP 문제와 비슷하다. 모든 DP 문제가 그렇듯 n = 1일 때, 2일 때, 3일 때 ... ... 를 구해보면 패턴이 보인다. 그리고 그 패턴에서 나는 다음과 같은 점화식을 세웠다. dp[i] = dp[i - 2] + dp[i - 1] 풀이 package src.dp; import java.io.BufferedReader; import java.io.InputStreamReader; public class Tiling { public static void main(String[] args) throws Exception { BufferedReader br = new BufferedReader(new InputStreamReader(..

Algorithm 2024.01.07

[백준] 2775: 부녀회장이 될테야 - Java (DP)

목 차 문제 접근 방식 풀이 문제 접근 방식 먼저 기본값인 [0] 층의 1~14호 까지를 입력한다. 그리고 [1] 층의 1~14호 까지 입력한다. 그리고 더욱 정확한 비교를 위해서 [2]층의 일부분 호수를 입력한다. 처음 숫자는 모두 1로 동일하다. 생각해 보면 [k][n - 1]은 이미 구했던 [k - 1][1] 부터 [k - 1][n - 1] 까지의 합이다. 그럼 여기에 아래층의 같은 호수만 더하면 현재 호수가 된다. 말이 좀 복잡한데 그림으로 알아보자. 먼저 표를 확인 훑고 아래 이미지를 확인해 보자. k 층의 n 호 dp[k][n] [0][n] = 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14 [1][n] = 1, 3, 6, 10, 15, 21, 28, 36, ..

Algorithm 2024.01.07

[백준] 2839: 설탕 배달 - Java (DP)

목 차 문제 접근 방식 풀이 문제 접근 방식 사실 DP 문제는 점화식만 잘 짜면 그 뒤로는 쉽다. 그래서 나는 DP 문제를 마주하면 먼저 나 혼자 계산해 본다. n = x 일 때 => 봉지 개수 n = 3 ⇒ 1 n = 4 ⇒ -1; n = 5 ⇒ 1 n = 6 ⇒ 2 n = 7 ⇒ -1; n = 8 ⇒ 2 n = 9 ⇒ 3 n = 10 ⇒ 2 n = 11 ⇒ 3 n = 12 ⇒ 4 n = 13 ⇒ 3 n = 14 ⇒ 4 n = 15 ⇒ 3 n = 16 ⇒ 4 n = 17 ⇒ 5 n = 18 ⇒ 4 n = 19 ⇒ 5 n = 20 ⇒ 4 n = 21 ⇒ 5 ... ... 먼저 보면 n 에서는 3과 5만 더할 수 있다. 그 말은 즉, dp[n] 은 n - 5 혹은 n - 3 에서 하나를 더한 값이 된다는 ..

Algorithm 2024.01.07

[백준] 10844: 쉬운 계단 수 - Java (DP)

목 차 문제 접근 방식 풀이 문제 접근 방식 나는 먼저 N=1, 2, 3, 4일 때를 가정해서 손으로 직접 작성해 보았다. [숫자] 는 해당 숫자로 끝나는 수를 말한다. 각 n 마다 0~3만 해보아도 알 수 있다. 핵심 n = 3일 때를 가정해 보자. 0과 9를 제외하면 모두 n - 1 에서 그 전 숫자와 그 다음 숫자의 합이라는 것을 알 수 있다. 말로 하면 어려운데 n = 3이고 2로 끝나는 수를 보자. 212, 232, 432 이렇게 3개 이다. 이제 다시 n - 1(= 2)이고, 1로 끝나는 수와 3으로 끝나는 수를 보자. 21, 23, 43 이렇게 3개 이다. 다시 돌아가 n = 3, 2로 끝나는 수를 보면 지금 이 숫자들에 2를 붙인 수들이다. 그럼이제 점화식을 세울 수 있게된다. 1~8로 끝..

Algorithm 2024.01.07