[백준] 12101 : 1, 2, 3 더하기 2 JAVA 풀이

1, 2, 3을 더해서 N을 만들 수 있는 경우의 수는

1, 2, 3으로 N-1, N-2, N-3을 만들 수 있는 경우의 수를 더하는 것으로 구할 수 있다.

예를 들어 5를 만들려면 4, 3, 2에 각각 1, 2, 3을 더하면 5를 만들 수 있다.

그러니 4, 3, 2를 만드는 경우의 수를 각각 구하면 되는 것이다.

 

이번 문제는 N을 1, 2, 3의 합으로 나타낸 식 중 원하는 식을 출력하는 것이다.

그러기 위해서는 1부터 N까지 각자의 수를 1, 2, 3의 합으로 표현한 식이 필요하다.

하지만 숫자에 따라서 그 식의 개수는 달라지기 때문에 ArrayList를 사용했다.

String형의 ArrayList 배열을 만들고, 각각의 ArrayList에는 1, 2, 3으로 그 수를 나타내는 식을 저장하는 방식이다.

 

우선 1, 2, 3을 이용해 1 2 3을 만드는 식을 초기화해둔다.

그리고 인덱스 4부터 N까지 자기보다 1, 2, 3 작은 수를 만드는 식에 3, 2, 1을 더하는 식을 자기 자리에 저장한다.

K번째 식이 존재한다면 N을 만드는 식을 오름차순 정렬한 뒤 K번째 식을 출력하고,

그렇지 않으면 -1을 출력한다.

import java.io.*;
import java.util.*;
public class Main{
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        String str[] = br.readLine().split(" ");
        int N = Integer.parseInt(str[0]);
        int K = Integer.parseInt(str[1]);
        
        // 1, 2, 3의 합으로 1 2 3을 만들 수 있는 식을
        // 초기값으로 줘야 하는데
        // 배열의 크기를 N+1로 하면,
        // N으로 1이나 2가 입력됐을 때 문제가 발생하니 N+3 크기로 선언
        ArrayList<String>[] arr = new ArrayList[N+3];
        
        for(int i=0;i<N+3;i++) {
        	// 1, 2, 3의 합으로 i를 만들 수 있는 식을 저장하기 위한 공간 생성
        	arr[i] = new ArrayList<>();
        }
        
        // 1 2 3을 만들 수 있는 식을 저장
        arr[1].add("1");
        arr[2].add("1+1");
        arr[2].add("2");
        arr[3].add("1+1+1");
        arr[3].add("1+2");
        arr[3].add("2+1");
        arr[3].add("3");
        
        // 자기보다 1, 2, 3 작은 수를 만드는 식에
        // 3 2 1을 더하는 식을 자기 자리에 저장
        for(int i=4;i<=N;i++) {
        	for(int j=1;j<=3;j++) {
        		for(String op : arr[i-j]) {
        			arr[i].add(op+"+"+j);
        		}
        	}
        }
        
        // 존재하지 않는 식을 찾으려고 한다면 -1 출력
        if(arr[N].size()<K) {
        	System.out.println(-1);
        }
        // 존재하는 식이라면, N을 만드는 식을 오름차순 정렬한 뒤에 출력
        else {
			Collections.sort(arr[N]);
        	System.out.println(arr[N].get(K-1));
        }
        
    }
    
}

https://velog.io/@jkh9615/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EB%B0%B1%EC%A4%80-12101-1-2-3-%EB%8D%94%ED%95%98%EA%B8%B0-2-Java

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

이 포스트를 참고했습니다!