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

문제 정보

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

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

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

풀이

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

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

알고리즘
1. ArrayList<String> 배열을 만들자.
2. ArrayList<String> 배열을 초기화 해주자.
3. n=1, 2, 3일 때에 수식을 ArrayList에 넣어주자
4. for i = 4 to n 까지 돌면서,
   ArrayList[i-1]에 있는 수식에 +1을,
   ArrayList[i-2]에 있는 수식에 +2을,
   ArrayList[i-3]에 있는 수식에 +3을 붙여준다.
5. ArrayList[n]에 있는 list의 갯수가 k보다 작다면 -1을 출력,
   아니라면, ArrayList[n]을 정렬하고, k번째 item을 출력한다.

[설명]
4를 만들어보자.

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

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

코드

import java.util.*;
public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int k = sc.nextInt();
		//1. ArrayList<String> 배열을 만들자.
		ArrayList<String>[] arr = new ArrayList[n+3];
		
		//2. ArrayList<String> 배열을 초기화 해주자.
		for(int i = 0; i <= n+2; i++)
			arr[i] = new ArrayList<>();			
		
		//3. n=1, 2, 3일 때에 수식을 ArrayList에 넣어주자
		arr[1].add("1");
		arr[2].add("1+1");
		arr[2].add("2");
		arr[3].add("1+2");
		arr[3].add("1+1+1");
		arr[3].add("2+1");
		arr[3].add("3");
		
		//4. for i = 4 to n 까지 돌면서,
		for(int i = 4; i <= n; i++) {
			/* ArrayList[i-1]에 있는 수식에 +1을,
			   ArrayList[i-2]에 있는 수식에 +2을,
			   ArrayList[i-3]에 있는 수식에 +3을 붙여준다. */
			for(int j = 1; j <= 3; j++) {
				for(String op : arr[i-j]) {
					arr[i].add(op + "+" + j);
				}
			}
		}
		
		/*5. ArrayList[n]에 있는 list의 갯수가 k보다 작다면 -1을 출력,
   		   	  아니라면, ArrayList[n]을 정렬하고, k번째 item을 출력한다.*/
		if(arr[n].size() < k) {
			System.out.println(-1);
		}else {
			Collections.sort(arr[n]);
			System.out.println(arr[n].get(k-1));
		}
	}
}

더 많은 정답 코드

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