[알고리즘] 백준 9095 1, 2, 3 더하기 Java

문제 정보

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

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

O(n) 풀이 : 시간제한 ok
자료형 : n은 최대 10이므로 int

풀이

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

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


설명
4를 만들어보자.

1을 만드는 경우에 3을 더해주고,
2를 만드는 경우에 2를 더해주고,
3을 만드는 경우에 1을 더해주면 4가 된다.
이해를 위해 그림을 준비했다. 어렵지 않다.

참고로 1, 2, 3까지는 각각 자기 자신이 들어올 수 있으므로 1,2,3까지는 경우의수를 미리 dp에 입력하고, 4부터 dp를 돌린다.

또한, n은 최대 10이고, 입력으로 무슨 값이 올지 모르므로 (첫 줄은 TestCase의 갯수일 뿐, TestCase의 Max값이 아님) 미리 dp를 최대값인 10까지 채워넣고 정답을 출력한다.

코드

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[11];
        dp[1] = 1;
        dp[2] = 2;
        dp[3] = 4;
        for(int i = 4; i < 11; i++)
        	dp[i] = dp[i-1] + dp[i-2] + dp[i-3];
        for(int i = 0; i < n; i++){
        	int t = stoi(br.readLine());
        	sb.append(dp[t] + "\n");
        }
        System.out.println(sb);
    }
	public static int stoi(String str) {return Integer.parseInt(str);}
}

더 많은 정답 코드

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