백준 5557번: 1학년 (Python/Java)

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

5557번: 1학년

 

 

 

접근

---

점화식만 제대로 찾는다면 어렵지 않게 풀 수 있는 문제다. 예제를 통해 풀이를 생각해보자. 총 열한 개의 숫자가 주어지고, 숫자 배열은 [8, 3, 2, 4, 8, 7, 2, 4, 0, 8, 8]이다. 여기서 배열의 가장 마지막 수는 연산을 통해서 '만들어야 하는 숫자'지 실제 연산에 쓰이는 숫자가 아니다. 즉, 우리가 실제로 쓸 숫자 배열은 마지막 인덱스 숫자를 뺀 [8, 3, 2, 4, 8, 7, 2, 4, 0, 8]이다.

 

우선 다이나믹 프로그래밍을 위한 배열을 만들어주자. 2차원 배열로 만들어줬는데, (주어진 숫자 개수-1)과 숫자 범위(0~20)까지를 열과 행으로 설정해줬다. 열을 주어진 (주어진 숫자 개수-1)로 설정한 이유는 주어진 숫자 중 가장 마지막 숫자는 연산에 쓰이는 숫자가 아니라 만들어야 하는 숫자기 때문이다. 각 배열 값은 주어진 숫자 배열의 인덱스 번호에서 연산을 수행했을 때, 연산 값이 나올 수 있는 횟수를 나타낸다.

 

이해가 잘 되지 않는다면, 첫 번째 숫자를 생각해보자. 가장 첫 번째 숫자인 8은 다른 숫자를 더하고 빼고 가 없다. 그냥 집어넣는다. 8은 숫자 배열의 0번 인덱스 값이다. 0번 인덱스를 연산할 때 8이 나올 수 있다. 즉, 배열 dp[0][8]은 1이 된다. dp[0][8]은 숫자 배열 인덱스 번호와 그 위치에서 나올 수 있는 연산 값을 나타내고, 1은 그 값이 나올 수 있는 횟수를 나타낸다. 이제 어느 정도 이해가 갈 것이다.

 

두 번째 숫자부터는 단순 반복이 이어진다. 숫자 배열 인덱스 번호에 해당하는 값을 가져온다. 그리고 직전에 연산했던 값에 더하거나 빼서 범위 안에 들어간다면 다이나믹 프로그래밍 배열에 1씩 더해주는 것이다. 나는 이를 아래와 같은 코드를 이용해 구했다. (예시는 자바로 작성되었다.)

 

// 첫번째 숫자 8은 이미 dp 배열 안에 넣어줬기 때문에 1부터 연산을 수행한다.
// 또한 마지막 숫자는 연산을 수행하는 값이 아니기 때문에 전체 숫자보다 1 뺀 값만큼 반복을 수행한다.
for(int i = 1 ; i < allNum-1 ; i++){
    // 0부터 20까지 for문을 돌려본다.
    // 직전 연산 값을 찾는 과정이다.
    for(int j = 0 ; j < 21 ; j++){
        // 만일 횟수를 세는 배열 값이 0이 아니라면 직전 연산에서 해당 숫자가 나왔다는 뜻이다.
        if(dp[i-1][j] != 0){
            if((j + numList[i]) <= 20){
                dp[i][j + numList[i]] += dp[i-1][j];
            }

            if((j - numList[i] >= 0)){
                dp[i][j - numList[i]] += dp[i-1][j];
            }
        }
    }
}

 

해당 연산을 통해 구한 값을 통해 결과를 출력하면 된다.

 

 

 

풀이

---

Python

allNum = int(input())
numList = list(map(int, input().split()))

dp = [[0 for i in range(21)] for i in range(allNum-1)]
dp[0][numList[0]] = 1

for i in range(1, allNum-1):
    for j in range(21):
        if dp[i-1][j] != 0:
            if (j + numList[i]) <= 20 :
                dp[i][j + numList[i]] += dp[i-1][j]

            if (j - numList[i]) >= 0:
                dp[i][j - numList[i]] += dp[i-1][j]

print(dp[allNum-2][numList[allNum-1]])

 

Java

import java.util.Scanner;

public class Main {
    
    public static void main(String[] args) {
        
        Scanner scan = new Scanner(System.in);

        int allNum = Integer.parseInt(scan.nextLine());
        String[] firstLine = (scan.nextLine()).split(" ");
        int[] numList = new int[allNum];
        for(int i = 0 ; i < allNum ; i++){
            numList[i] = Integer.parseInt(firstLine[i]);
        }

        long[][] dp = new long[allNum-1][21];
        dp[0][numList[0]] = 1;

        for(int i = 1 ; i < allNum-1 ; i++){
            for(int j = 0 ; j < 21 ; j++){
                if(dp[i-1][j] != 0){
                    if((j + numList[i]) <= 20){
                        dp[i][j + numList[i]] += dp[i-1][j];
                    }

                    if((j - numList[i] >= 0)){
                        dp[i][j - numList[i]] += dp[i-1][j];
                    }
                }
            }
        }

        System.out.println(dp[allNum-2][numList[allNum-1]]);

    }

}