[백준] 12101 - 1,2,3 더하기 2 (Java)

[백준] 12101 - 1,2,3 더하기 2 (Java)

문제

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

풀이/후기

1,2,3 더하기 문제 중 9095번 문제를 복습하고 풀어보았다.

그치만 9095번에서 패턴을 찾아낸 것으로만은 풀지 못했다.

ArrayList를 이용해 문자열 배열을 활용해서 푸는 방법이 포인트였던 것 같다.

수식을 출력해내는 부분도 좀 헷갈렸는데

아래 그림을 보니 그냥 똑같이 생각해주면 된다는 것을 깨달았다.

역시 직접 눈으로 봐야 이해가 가는 편,,^^;

출처 : velog 방방다망함

 

코드

package DynamicProgramming;

import java.io.*;
import java.util.*;

public class Problem12101 {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer str = new StringTokenizer(br.readLine(), " ");
		
		int N = Integer.parseInt(str.nextToken());
		int K = Integer.parseInt(str.nextToken());
		
		ArrayList<String>[] list = new ArrayList[N+3];		//3이하의 입력값 대비
		
		for (int i=0; i < N+3; i++) {
			list[i] = new ArrayList<>();
		}
		
		list[1].add("1");
		
		list[2].add("1+1");
		list[2].add("2");
		
		list[3].add("1+1+1");
		list[3].add("1+2");
		list[3].add("2+1");
		list[3].add("3");
		
		for (int i=4; i < N+1; i++) {
			for (int j=1; j <= 3; j++) {
				for (String st : list[i-j]) {
					list[i].add(st + "+" + j);
				}
			}
		}
		
		StringBuilder sb = new StringBuilder();
		if (K > list[N].size()) sb.append(-1);
		else {
			Collections.sort(list[N]);
			sb.append(list[N].get(K-1));
		}
		
		System.out.println(sb);
	}
}

Commit

https://github.com/allrightDJ0108/CodingTestStudy/commit/ae2d22d936b82037e5b124755504a95cc3e7b480

참고

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