[알고리즘] 백준 15989 1, 2, 3 더하기 (4) Java

문제 정보

플랫폼 : 백준
분류 : Dynamic Programming (동적 프로그래밍)
난이도 : 실버1
링크 : https://www.acmicpc.net/problem/15989

시간제한 및 메모리 제한 검증

O(n) 풀이 : 시간제한 ok
자료형 : int

풀이

주말동안 Dynamic Programming 유형인 [1, 2, 3 더하기] 시리즈의 문제를 풀어봤다.
사실 어제부터 포스팅을 하려고 했는데, 머리자르느라 시간이 늦어서 쉬었다.

만약, 이전 1, 2, 3 더하기 시리즈를 풀지 않았거나, 풀이를 보지 않았다면 이곳을 클릭하여 이전 풀이를 먼저 보고오자!

점화식
dp[i][1] = dp[i-1][1];
dp[i][2] = dp[i-2][1] + dp[i-2][2];
dp[i][3] = dp[i-3][1] + dp[i-3][2] + dp[i-3][3]; (n >= 4)

문제가 생각할게 많아졌다. 일단, 기존 1차원 배열이었던 점화식이 2차원배열로 바뀌었다.
dp[i][j] 에서 i: 임의의 정수, j: 수식이 j로 끝남
을 의미한다. 예시를 들어보면,

위 사진과 같다. 여기서 반드시 주의해야할 사항이 있다.
중복을 지원하지 않기 때문에, 수식은 오름차순으로 정렬돼있어야 한다.
그렇지 않으면, 수식이 중복되거나 문제가 안풀리는 어마무시한(?) 고통이 따른다.

왜 오름차순으로 정렬해야하는지는 아래 사진을 통해 대신 대답한다.

[점화식 설명]

4를 1, 2, 3의 합으로 나타내보자.
1을 만드는 경우에 3을 더해주고,
2를 만드는 경우에 2를 더해주고,
3을 만드는 경우에 1을 더해주면 4가 된다.
그러나, 우리는 오름차순으로 값을 구해야한다.

1) 4를 만들 수 있는 수식 중에서, 1로 끝나는 수식은 3을 만드는 수식에서 1을 더하는 것이다.
즉, dp[4][1] = dp[3][1]이다. 일반화하면, dp[n][1] = dp[n-1][1] 이다.

2) 4를 만들 수 있는 수식 중에서, 2로 끝나는 수식은 2를 만드는 수식에서 1로 끝나는 것과 2로 끝나는 것에 2를 더하는 것이다.
즉, dp[4][2] = dp[3][2] + dp[3][1]이다. 일반화하면, dp[n][2] = dp[n-2][1] + dp[n-2][2] 이다.

3) 4를 만들 수 있는 수식 중에서, 3으로 끝나는 수식은 1를 만드는 수식에서 1, 2, 3으로 끝나는 것에 3을 더하는 것이다.
즉, dp[4][3] = dp[1][1] + dp[1][2] + dp[1][3] 이다.
(물론, 1은 2나 3으로 끝나는 경우가 없으므로, dp[1][2] = 0, dp[1][3] = 0이다.)
일반화하면, dp[n][3] = dp[n-3][1] + dp[n-3][2] + dp[n-3][3] 이다.

위와 같은 과정을 통해
dp[i][1] = dp[i-1][1];
dp[i][2] = dp[i-2][1] + dp[i-2][2];
dp[i][3] = dp[i-3][1] + dp[i-3][2] + dp[i-3][3]; (n >= 4)라는 점화식이 나온다.

코드

import java.io.*;
public class Main {
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		int n = stoi(br.readLine());
		int[][] dp = new int[10001][4];
		dp[1][1] = 1; // 1
		dp[2][1] = 1; // 1+1
		dp[2][2] = 1; // 2
		dp[3][1] = 1; // 1+1+1
		dp[3][2] = 1; // 1+2
		dp[3][3] = 1; // 3
		
		for(int i = 4; i <= 10000; i++) {
			dp[i][1] = dp[i-1][1];
			dp[i][2] = dp[i-2][1] + dp[i-2][2];
			dp[i][3] = dp[i-3][1] + dp[i-3][2] + dp[i-3][3];
		}
		
		for(int i = 0; i < n; i++) {
			int t = stoi(br.readLine());
			sb.append(dp[t][1] + dp[t][2] + dp[t][3] + "\n");
		}
		System.out.println(sb);
	}
	public static int stoi(String str) {return Integer.parseInt(str);}
}

더 많은 정답 코드

블로그를 쓰기 이전에 풀어본 문제들이 많다. 해설강의는 없지만, 백준 문제의 풀이 코드가 필요한 경우 이곳을 클릭하여 소스코드를 참조해보도록 하자. 단, 코드만 복사-붙여넣기 하는것은 본인에게 결코 도움이 되지 않는다. 반드시 먼저 생각해보고, 막히는 경우에 참고하고 왜 이렇게 코드가 작성됐는지를 다시 한 번 생각해보는 습관을 들이자.