백준 12101번 <1, 2, 3 더하기 2>

백준 알고리즘 12101번

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

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

9095번에서 발전된 문제

 

처음에는!!!!

2차원 배열을 사용해서 풀었다.

 

그런데 자꾸 런타임 에러가 나서 으으으음!!! 이러면서 ArrayList를 사용해서 풀었다.

(ArrayList 안의 원소는 LinkedList형이다.)

 

굳이라는 생각이 들었지만 혹시 2차원 배열에 빈 공간이 너무 많아서 그런가 하고 이렇게 풀었는데

 

알고 보니까 2차원 배열의 크기를 알맞지 않게 해서 런타임 에러가 뜬 거였다...

멍청해.... ㅠㅠ

 

굳이라고 생각이 드는 ArrayList가 아니라 2차원 배열을 사용한 것을 포스팅할 거다!!

(어차피 2차원 배열로 만드는 것을 ArrayList로 바꾼 것뿐이라 알고리즘은 딱히 다른 게 없다.)

---

12101번

입력으로 들어오는 정수 n(양수)과 k로

n을 1, 2, 3의 합으로 나타내는 방법 중에서 사전 순으로 k번째에 오는 것을 출력해준다.

만약 k번째 오는 식이 없는 경우에는 -1을 출력한다.

---

문제 해결

일단 answer이라는 int형 2차원 배열을 생성했다.

 

백준 알고리즘 9095번에서 보면 10일 때 1, 2, 3의 합으로 나타내는 방법의 수는 274이다.

 

그래서 2차원 배열을 new int[11][275]로 생성했다.

-> 입력으로 주어지는 n이 11보다 작으니까 n의 최댓값은 10이다. 

     0은 빼고 1부터 10까지 하려고 11로 해주었다.

-> 입력으로 주어지는 k가 0이 아니라 1부터 시작하기 때문에 

    배열의 크기를 274가 아니라 274+1인 275로 해주었다. (이거 때문에 런타임 에러 뜸...)

 

1. answer[N][0]에는 N을 1, 2, 3의 합으로 나타내는 방법의 수를 구해서 저장한다.

   (9095번의 코드를 이용해서 구한다.)

 

2. 만약 answer[n][0]의 값이 k보다 작으면 = k번째 오는 식이 없다.

   -1을 출력한다.

 

3. 2번의 조건을 만족하지 않으면

   9095번의 코드를 활용해서 2차원 배열을 채워준다.

 

2차원 배열 채워주기.

answer[1][0]은 1로, answer [1][1]은 "1"로 미리 채운다.

 

for문을 2부터 n까지 돌린다. (for문의 변수를 i라고 했을 때)

i - 1 은 1+### 이런 형식으로 사전 순에서 처음 부분

i - 2 는 2+### 이런 형식으로 사전 순에서 중간 부분

i - 3 는 3+### 이런 형식으로 사전 순에서 끝 부분

 

for문 안에서는 i가 2, 3일 때는 예외처리를 해주어야 한다.

(i가 2면 i-2와 i-3 부분을 할 필요가 없고 i가 3일 때는 i-3부분을 할 필요가 없기 때문에)

 

만약 i가 4라면 

i - 1 = 3으로 1 + (3을 1, 2, 3의 합으로 나타내는 방법)을 차례대로 구해서 배열에 넣어주면 된다.

3을 1, 2, 3의 합으로 나타내는 방법들은 answer[3]에 저장되어 있다.

answer[3][0]으로 3을 1, 2, 3의 합으로 나타내는 방법의 수를 알 수 있으니까 그만큼 for문을 돌려서

answer[4][1] = 1+answer[3][1]

answer[4][2] = 1+answer[3][2]

answer[4][3] = 1+answer[3][3]

answer[4][4] = 1+answer[3][4]

이렇게 넣어주면 된다.

 

i - 2 = 2 으로 2 + (2를 1, 2, 3의 합으로 나타내는 방법)을 차례대로 구해서 배열에 넣어주면 된다.

2를 1, 2, 3의 합으로 나타내는 방법들은 answer[2]에 저장되어 있다.

answer[2][0]으로 2를 1, 2, 3의 합으로 나타내는 방법의 수를 알 수 있으니까 그만큼 for문을 돌려서

answer[4][answer[3][0]+1] = 2+answer[2][1]

answer[4][answer[3][0]+2] = 2+answer[2][2]

이렇게 넣어주면 된다.

 

i - 3 = 1으로 3 + (1를 1, 2, 3의 합으로 나타내는 방법)을 차례대로 구해서 배열에 넣어주면 된다.

1를 1, 2, 3의 합으로 나타내는 방법들은 answer[1]에 저장되어 있다.

answer[1][0]으로 2를 1, 2, 3의 합으로 나타내는 방법의 수를 알 수 있으니까 그만큼 for문을 돌려서

answer[4][answer[3][0]+answer[2][0]+1] = 3+answer[1][1]

이렇게 넣어주면 된다.

 

위에 구하는 법을 표로 나타내 보면 아래와 같다.

파란 글씨는 1, 2, 3의 합으로 나타내는 방법의 수를 나타내고

핑크 화살표를 따라가면 어디서 나타난 숫자들인지 알 수 있다.

---

코드

import java.io.IOException;
import java.util.Scanner;

public class Main {

	public static void main(String[] args) throws IOException {

		Scanner sc = new Scanner(System.in);

		int num = sc.nextInt();
		int k = sc.nextInt();


		String[][] answer = new String[11][275];
		answer[1][0] = "1";

		for (int i = 2; i < (num + 1); i++) {
			int sub = i - 1;
			int result = Integer.parseInt(answer[sub][0]);

			if (sub == 1) {
				result++;
				answer[i][0] = String.valueOf(result);
				continue;
			}

			sub = i - 2;
			result += Integer.parseInt(answer[sub][0]);

			if (sub == 1) {
				result++;
				answer[i][0] = String.valueOf(result);
				continue;
			}

			sub = i - 3;
			result += Integer.parseInt(answer[sub][0]);
			answer[i][0] = String.valueOf(result);

		}

		answer[1][1] = "1";

		int check = Integer.parseInt(answer[num][0]);
		if (check < k) {
			System.out.println("-1");
		} else {
			for (int i = 2; i < num + 1; i++) {
				int sub = i - 1;
				int size = Integer.parseInt(answer[sub][0]);

				for (int j = 1; j < size + 1; j++) {
					answer[i][j] = "1+" + answer[sub][j];
				}

				if (sub == 1) {
					answer[i][2] = "2";
					continue;
				}

				sub = i - 2;
				int newSize = Integer.parseInt(answer[sub][0]);

				for (int j = 1; j < newSize + 1; j++) {
					answer[i][j + size] = "2+" + answer[sub][j];
				}
				size += newSize;

				if (sub == 1) {
					answer[i][4] = "3";
					continue;
				}

				sub = i - 3;
				newSize = Integer.parseInt(answer[sub][0]);

				for (int j = 1; j < newSize + 1; j++) {
					answer[i][j + size] = "3+" + answer[sub][j];
				}
			}

			System.out.println(answer[num][k]);
		}

	}

}

---

---