[백준, Java] 12101번, 1, 2, 3 더하기 2, (백트레킹)

문제 링크

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

---

주의사항

• JAVA를 사용하여 프로그램을 사용하였습니다.
• 백준에서 코드를 작성하였을 때 아래 형태에서 Main에서 결과가 출력되어야 합니다.

public class Main{ 	
	public static void main(String[] args){
    }
}

---

문제 설명

---

 

접근 방법

이 문제에 핵심

 

1. 정수를 1, 2, 3으로만 사용해서 합을 나타내는 방법만 가능하다.

2. 1 + 2 + 1, 1 + 1 + 2는 다른 것이며, 사전순으로 정렬하면 1 + 1 + 2가 먼저입니다.

3. 정수 N을 만드는 방법 중 K번째 방법의 수식을 결과로 출력합니다.

4. K번째가 존재하지 않을 경우 -1을 결과로 출력합니다.

 

알고리즘 진행 순서.

 

1. 입력된 정보를 저장합니다.

 

2. 백트레킹을 통해서 정수 N을 만드는 방법을 탐색합니다.

 

3. 탐색을 통해 얻은 K번째 수식을 결과로 출력합니다.

 

백트래킹(1, 2, 3 더하기 방법 탐색)

 

이 문제에서 가장 중요한 것은 사전순으로 정렬한 K번째 수식을 결과로 출력해야 하는 것입니다.

 

▶ 백트레킹을 진행할 때 작은 수부터 탐색을 진행하면 정렬하는 과정을 생략해도 됩니다.

 

Why??

 

백트레킹을 진행할 때 1부터 탐색을 진행하면 1부터 먼저 수식에 들어가기 때문입니다.

 

 

백트레킹 진행하는 과정

 

백트레킹에서 들어갈 수 있는 숫자 { 1, 2, 3 }을 정의한 뒤

 

N = 3일 때

 

1

 

1 + 1

 

1 + 1 + 1

 

1 + 2

 

3

 

또한, 이 문제에서는 K번째를 찾으면 이후 탐색은 불필요하기 때문에 K번째 방법을 찾았을 때 백트레킹을 모두 종료하시면 됩니다.

 

※예제 입력 과정을 살펴보시면 이해하시기 편하실 것입니다.

 

예제입력 1.

 

1. 입력된 정보를 저장합니다.

 

N : 4

 

K : 3

 

 

2. 백트레킹을 통해서 정수 N을 만드는 방법을 탐색합니다.

 

정수 N(4)을 만드는 백트레킹 과정 진행

 

 

 

1

 

1 + 1

 

1 + 1 + 1

 

1 + 1 + 1 + 1 : 1번째

 

1 + 1 + 2 : 2번째

 

1 + 2 + 1 : 3번째

 

K번째 방법을 찾았기 때문에 탐색을 종료합니다.

 

3. 탐색에서 얻은 최대 시간일 때 최대 점수를 결과로 출력합니다.

 

 

탐색을 통해 얻은 3번째 방법 : 1 + 2 + 1

 

1+2+1을 결과로 출력합니다.

 

 

• BufferedReader를 사용하여 입력되는 정보를 저장합니다.
• StringTokenizer를 이용하여  N, K의 정보를 띄어쓰기 기준 나누었습니다.
• search를 통해서 정수 N을 만드는 K번째 방법을 탐색합니다.
• 탐색이 끝났을 때 K번째 값이 존재하면 방법, 없으면 -1을 BufferedWriter 저장합니다.
• BufferedWriter에 저장된 결과를 출력합니다.

• search함수는 백트레킹을 통해서 정수 N을 만드는 방법을 탐색합니다.
• search함수는 사전 순 정렬이 되기 위해서 1, 2, 3순서로 탐색을 진행합니다.
• search함수는 K번째 방법을 탐색하였을 때 모든 탐색을 종료합니다.

결과코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;

public class Main {
    static int len, N, K;
    //백트레킹 탐색 진행할 1, 2, 3 배열
    static int[] num = {1, 2, 3};
    //백트레킹에 현재 방법에 속한 숫자들
    static int[] cur = new int[11];
    public static void main(String[] args) throws IOException {
        //입력값 처리하는 BufferedReader
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        //결과값 출력하는 BufferedWriter
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine()," ");
        //입력값 저장
        N = Integer.parseInt(st.nextToken());
        K = Integer.parseInt(st.nextToken());
        //백트레킹 진행
        search(0, 0);
        //K번째 방법이 존재하지 않을 경우
        if(K != 0){
            bw.write("-1");
        }else{	//K번째 방법이 존재할 때
            //K번째 방법에 대해서 '+' 수식 형식으로 설정
            StringBuilder result = new StringBuilder();
            for(int i = 0; i < len; i++) {
                result.append(cur[i]);
                result.append("+");
            }
            result.deleteCharAt(result.length()-1);
            //K번째 방법 BufferedWriter 저장
            bw.write(result.toString());
        }
        bw.flush();		//결과 출력
        bw.close();
        br.close();
    }
    //백트레킹을 통해서 1, 2, 3 방법을 탐색하는 함수입니다.
    static void search(int sum, int depth){
        if(sum == N){	//정수 N을 만들었을 때
            K--;		//K번째 방법을 찾기 위해 -1
            len = depth;	//현재 방법의 길이 저장
            return;
        }
        //다음 숫자 탐색
        for(int i=0;i<3;i++){
            //더했을 때 N을 넘어가거나, K번째 방법을 찾았을 때
            if(sum + num[i] > N || K == 0){
                break;
            }
            //다음 수 탐색
            cur[depth] = num[i];
            search(sum + num[i], depth + 1);
        }
    }
}