(22.03.18) (Baekjoon) 12101. 1,2,3 더하기 2

https://www.acmicpc.net/problem/12101

12101번: 1, 2, 3 더하기 2

1,2,3 더하기는 1~9 시리즈까지 있다. 이번엔 그 두번째 문제다.

1번 문제가 주어진 숫자를 1,2,3으로 만들 수 있는 경우의 수를 구하는 문제라고 한다면,

이번 문제는 n과 m이 주어진다 했을 때, n의 숫자를 1,2,3으로 만들 수 있는 경우들 중 m번째 경우를 구하는 문제다.

이때, 각 셈은 사전 순으로 주어진다.

ex ) 4의 경우

1 + 1 + 1 + 1

1 + 1 + 2

1 + 2 + 1

1 + 3

2 + 1 + 1

2 + 2

3 + 1

의 순서를 의미한다.

즉,n = 4, m = 1이라 하면 1+1+1+1이 나와야 한다.

 

DP가 으레 그렇듯 작은 문제로 쪼개서 접근하자.

 

1) 각 수의 셈을 어떻게 순서대로 정렬할 것인가

일단 이전 문제는 int가 나와야 하는 것과 달리 String이 나와야 한다.

그렇기에 1번 문제에서 dp[i][j] 라 하면 dp[i-1]에서 영향을 받듯이 이 문제에서도 그렇게 될 수 있게 만들어 줘야 한다.

1-1) 일단 기본적으로 생각할 수 있은 값을 보면,

1 => 1

2 => 1+1, 2

3 => 1+1+1, 1+2, 2+1, 3 이 있는데

 

이 기본 값을 이용해서 4부터 차근차근 채워나가야 한다.

이전 문제에서 알 수 있었듯

4 의 경우로 또 생각하면

1로 시작하고 뒤에 3을 만드는 경우가 올 수 있고

2로 시작하고 뒤에 2를 만드는 경우가 올 수 있으며

3으로 시작하고 뒤에 1로 만드는 경우가 올 수 있다.

1,2,3으로써 사전 순서가 성립되기 때문에 이를 구현해주기만 하면 된다.

 

 

2) n 과 m에 대응하는 셈을 어떻게 구현할 것인가.

특정 요소 안에 자연스럽게 값을 추가해줘야 하기 때문에 ArrayList를 활용하면 된다.

ArrayList list = new ArrayList[n+3];
		
		for (int i = 0; i < n+3; i++) {
			list[i] = new ArrayList<String>();
		}
		// List 1에 해당하는 값을 집어넣음
		list[1].add("1");
		
		// List 2에 해당하는 연산을 집어넣음
		list[2].add("1+1");
		list[2].add("2");
		// List 3에 해당하는 연산을 집어넣음
		list[3].add("1+1+1");
		list[3].add("1+2");
		list[3].add("2+1");
		list[3].add("3");

 

우선 n보다 3 많은 크기의 ArrayList를 선언해준 후, 1,2,3에 해당하는 기본 셈들을 넣어준다.

for (int i = 4; i <= n; i++) {
			for (int j = 1; j <= 3; j++) {
				for (String s : list[i-j]) { //i = 4 => j = 1 
//					ArrayList[i-1] 에 있는 수식에 +1을 (ex i == 4, j == 1 => ArrayList[4-1]에 +1)
//					 ArrayList[i-2] 에 있는 수식에 +2을 (ex i == 4, j == 2 => ArrayList[4-2]에 +2)
//					 ArrayList[i-3] 에 있는 수식에 +3을 (ex i == 4, j == 2 => ArrayList[4-3]에 +3)
					list[i].add(j + "+" + s); 
				}
			}
		}

이후 위에서 설명했듯이 4번부터 새로 값을 집어넣기 사작하여 

ArrayList[i-1] 에 있는 수식에 +1을 (ex i == 4, j == 1 => ArrayList[4-1]에 +1)
ArrayList[i-2] 에 있는 수식에 +2을 (ex i == 4, j == 2 => ArrayList[4-2]에 +2)
ArrayList[i-3] 에 있는 수식에 +3을 (ex i == 4, j == 2 => ArrayList[4-3]에 +3)

의 방식으로 값을 집어넣으면 된다.

list[i].add(j + "+" + s)

앞의 숫자가 1,2,3 중 하나가 먼저 오면 된다.

 

전체 코드(Java)

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.StringTokenizer;

public class Main {
	static int n,m;
	static int[][] ar;
	static ArrayList<String>[] list;
	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		n = Integer.parseInt(st.nextToken());
		m = Integer.parseInt(st.nextToken());
		
		list = new ArrayList[n+3];
		
		for (int i = 0; i < n+3; i++) {
			list[i] = new ArrayList<String>();
		}
		// List 1에 해당하는 값을 집어넣음
		list[1].add("1");
		
		// List 2에 해당하는 연산을 집어넣음
		list[2].add("1+1");
		list[2].add("2");
		// List 3에 해당하는 연산을 집어넣음
		list[3].add("1+1+1");
		list[3].add("1+2");
		list[3].add("2+1");
		list[3].add("3");
		
		//1,2,3은 모두 정해졌으므로 그 다음을 보면
		for (int i = 4; i <= n; i++) {
			for (int j = 1; j <= 3; j++) {
				for (String s : list[i-j]) { //i = 4 => j = 1 
//					ArrayList[i-1] 에 있는 수식에 +1을 (ex i == 4, j == 1 => ArrayList[4-1]에 +1)
//					 ArrayList[i-2] 에 있는 수식에 +2을 (ex i == 4, j == 2 => ArrayList[4-2]에 +2)
//					 ArrayList[i-3] 에 있는 수식에 +3을 (ex i == 4, j == 2 => ArrayList[4-3]에 +3)
					list[i].add(j + "+" + s); 
				}
			}
		}
		if(list[n].size() < m) {
			System.out.println(-1);
		}
		else {
			System.out.println(list[n].get(m-1));
		}