문제 정보
플랫폼 : 백준
분류 : 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을 출력한다.
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));
}
}
}
더 많은 정답 코드
블로그를 쓰기 이전에 풀어본 문제들이 많다. 해설강의는 없지만, 백준 문제의 풀이 코드가 필요한 경우 이곳을 클릭하여 소스코드를 참조해보도록 하자. 단, 코드만 복사-붙여넣기 하는것은 본인에게 결코 도움이 되지 않는다. 반드시 먼저 생각해보고, 막히는 경우에 참고하고 왜 이렇게 코드가 작성됐는지를 다시 한 번 생각해보는 습관을 들이자.