[BOJ G5][#DP]5557번 1학년

1학년 성공다국어

한국어   

시간 제한메모리 제한제출정답맞힌 사람정답 비율

1 초

128 MB

20695

9672

7583

46.812%

문제

상근이가 1학년 때, 덧셈, 뺄셈을 매우 좋아했다. 상근이는 숫자가 줄 지어있는 것을 보기만 하면, 마지막 두 숫자 사이에 '='을 넣고, 나머지 숫자 사이에는 '+' 또는 '-'를 넣어 등식을 만들며 놀고 있다. 예를 들어, "8 3 2 4 8 7 2 4 0 8 8"에서 등식 "8+3-2-4+8-7-2-4-0+8=8"을 만들 수 있다.

상근이는 올바른 등식을 만들려고 한다. 상근이는 아직 학교에서 음수를 배우지 않았고, 20을 넘는 수는 모른다. 따라서, 왼쪽부터 계산할 때, 중간에 나오는 수가 모두 0 이상 20 이하이어야 한다. 예를 들어, "8+3+2-4-8-7+2+4+0+8=8"은 올바른 등식이지만, 8+3+2-4-8-7이 음수이기 때문에, 상근이가 만들 수 없는 등식이다.

숫자가 주어졌을 때, 상근이가 만들 수 있는 올바른 등식의 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 숫자의 개수 N이 주어진다. (3 ≤ N ≤ 100) 둘째 줄에는 0 이상 9 이하의 정수 N개가 공백으로 구분해 주어진다.

출력

첫째 줄에 상근이가 만들 수 있는 올바른 등식의 개수를 출력한다. 이 값은 263-1 이하이다.

예제 입력 1 복사

11
8 3 2 4 8 7 2 4 0 8 8

예제 출력 1 복사

10

예제 입력 2 복사

40
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 1 1

예제 출력 2 복사

7069052760

 

 

📝 풀이

처음은 역시 BFS로 완전탐색을 진행해보었다.

 

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

public class Main {
    static long result = 0;
    static int N;
    static int num[];
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        num = new int[N + 1];
        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 1; i <= N; i++) {
            num[i] = Integer.parseInt(st.nextToken());
        }
        bfs();
        System.out.println(result);
    }

    public static void bfs() {
        Queue<int[]> q = new LinkedList<>();
        q.add(new int[] {1, num[1]});
        
        while (!q.isEmpty()) {
            int arr[] = q.poll();
            int idx = arr[0];
            int total = arr[1];

            if (idx+1 == N) {
                if (total == num[N]) {
                    result++;
                }
                continue;
            }
            
            if (idx + 1 < N && total + num[idx + 1] <= 20) {
                q.add(new int[] {idx + 1, total + num[idx + 1]});
            }

            if (idx + 1 < N && total - num[idx + 1] >= 0) {
                q.add(new int[] {idx + 1, total - num[idx + 1]});
            }
        }
    }
}

 

DP할때 보는 늘 익숙한 그장면..

 

자 이제 BFS로 못푸는 DP 문제이니 DP 구현을 생각하였다.

현재 필요한 상태는 2가지이다. 계산을 할 인덱스와 어떤 수가 나왔는지를 표시해야한다.

그렇기에 이 문제는 2차원 배열로 DP 문제를 구현하였다.

dp[인덱스][나온 수]

 

코드 자체는 어렵지 않기에 이해는 쉬울 것이다.

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

public class Main {
    static long dp[][];
    static int N;
    static int num[];
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        num = new int[N + 1];
        dp = new long[N + 1][21];
        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 1; i <= N; i++) {
            num[i] = Integer.parseInt(st.nextToken());
        }
        dp[1][num[1]] = 1;

        for(int i = 1; i < N; i++){
            for(int j = 0; j <= 20; j++){
                if(dp[i][j] != 0){
                    if(j + num[i + 1] <= 20){
                        dp[i + 1][j + num[i + 1]] += dp[i][j];
                    }
                    if (j - num[i + 1] >= 0) {
                        dp[i + 1][j - num[i + 1]] += dp[i][j];
                    }
                }
            }
        }

        System.out.println(dp[N-1][num[N]]);
    }
}