[백준] code.plus(다이나믹 프로그래밍,JAVA)5557번, 1학년

문제 링크

5557번: 1학년

---

주의사항

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

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

---

문제 설명

---

접근 방법

동적 계획법

모든 연산을 수행하면 똑같은 연산을 중복되게 수행하게 되는데 다이나믹 프로그램은 연산한 내용을 따로 저장하여 효율적으로 작성한 프로그램입니다.

 

이 문제에 핵심은

 

1. 상근이는 음수와 20이 넘는 수를 배우지 않았습니다.

2. 입력되는 숫자의 마지막 두 숫자에 '='을 넣고 나머지 숫자 사이에는 '+' , '-'를 끼어넣습니다.

3. 연산 중 음수나 20이 넘으면 그 연산을 계산할 수 없습니다.

4. 상근이가 연산을 해결할 수 있는 개수를 결과로 출력합니다.

 

알고리즘 진행 순서.

 

1. 입력되는 숫자들을 저장합니다.

 

2. 연산을 만들어가면서 상근이가 해결할 수 있는 개수를 DP[][]에 저장합니다.

 

3. DP[][]의 최대값을 결과로 출력합니다.

 

 

DP[i][j]의 형태

 

i : i번째 숫자일 때

j : 현재 연산의 결과

 

i번째 숫자까지  연산한 결과가 j일때 상근이가 해결할 수 있는 연산의 개수를 DP[i][j]에 저장합니다.

 

 

예제입력 1.

 

1. 입력되는 숫자들을 저장합니다.

 

N : 11

Num : 8 3 2 4 8 7 2 4 0 8 8

 

2. 연산을 만들어가면서 상근이가 해결할 수 있는 개수를 DP[][]에 저장합니다.

 

※문자가 같을 때만 DP를 저장하는 것을 표현하였습니다.

 

8 + 3 : 11

8 - 3 : 5

 

8 + 3 + 2 : 13

8 + 3 - 2 : 9

8 - 3 + 2 : 7

8 - 3 - 2 : 3

 

8 + 3 + 2 + 4 : 17

8 + 3 + 2 - 4 : 9

8 + 3 - 2 + 4 : 13

8 + 3 - 2 - 4 : 5

8 - 3 + 2 + 4 : 11

8 - 3 + 2 - 4 : 3

8 - 3 - 2 + 4 : 7

8 - 3 - 2 - 4 : -1(X)

 

8 + 3 + 2 + 4 + 8 : 25(X)

8 + 3 + 2 + 4 - 8 : 9

8 + 3 + 2 - 4 + 8 : 17

8 + 3 + 2 - 4 - 8 : 1

8 + 3 - 2 + 4 + 8: 21(X)

8 + 3 - 2 + 4 - 8 : 5

8 + 3 - 2 - 4 + 8 : 13

8 + 3 - 2 - 4 - 8 : -3(X)

8 - 3 + 2 + 4 + 8: 19

8 - 3 + 2 + 4 - 8 : 3

8 - 3 + 2 - 4 + 8 : 11

8 - 3 + 2 - 4 - 8 : -5(X)

8 - 3 - 2 + 4 + 8 : 15

8 - 3 - 2 + 4 - 8 : -1(X)

 

.... 

 

3. DP[][]의 최대값을 결과로 출력합니다.

 

DP[][]의 최대값(10)을 결과로 출력합니다.

 

• BufferedReader를 사용하여 입력 값을 받았습니다.
• StringTokenizer를 이용하여 숫자들을 나누었습니다.
• search함수를 실행하여 상근이가 해결할 수 있는 연산의 개수를 BufferedWriter에 저장합니다.
• BufferedWriter에 저장된 결과값을 출력하였습니다.

• search함수는 DP[][]와 재귀를 통해서 상근이가 해결할 수 있는 연산의 개수를 구합니다.
• search함수에서 중간에 연산의 값이 0~20을 벗어나면 해당 연산을 종료합니다. 

 

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

public class Main {
    static int N;
    static int[] num;	//입력되는 숫자 저장 배열
    static long[][] DP;	//상근이가 해결하는 연산 개수 저장하는 메모이제이션 배열
    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));
        N = Integer.parseInt(br.readLine());
        num = new int[N];
        DP = new long[N+1][21];
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        //입력되는 숫자들 저장
        for(int i=0;i<N;i++)
            num[i] = Integer.parseInt(st.nextToken());

        //숫자들의 연산을 만들어가며 만들 수 있는 연산의 개수를 구해서 BufferedWriter 저장
        bw.write(search(1, num[0], String.valueOf(num[0])) + "");
        bw.flush();		//결과 출력
        bw.close();
        br.close();
    }
    //상근이가 숫자들을 이용해서 해결할 수 있는 연산의 개수를 구하는 함수
    static long search(int count, int value, String str){

        if(count==N-1){	//연산 완성시
            if(num[N-1] == value){
                return 1;
            }
            return 0;
        }

        if(DP[count][value]!= 0)	//먼저 방문했을 경우
            return DP[count][value];

        if(value + num[count] <= 20)	// +
            DP[count][value] += search(count+1, value + num[count], str + "+" + num[count]);

        if(value - num[count] >=0)	// -
            DP[count][value] += search(count+1, value - num[count], str + "-" + num[count]);

        return DP[count][value];
    }
}