[BOJ/JAVA] 5557번: 1학년

5557번: 1학년

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

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

키워드

• 마지막 두 숫자 사이에 '='을 넣고, 나머지 숫자 사이에는 '+' 또는 '-'를 넣어 등식을 만들며 놀고 있다.

• 상근이는 아직 학교에서 음수를 배우지 않았고, 20을 넘는 수는 모른다.

• 상근이가 만들 수 있는 올바른 등식의 수를 구하는 프로그램

---

구현

• 초기값은 항상 맨 앞에 있는 숫자이다.

• 결과 값은 항상 맨 마지막에 있는 숫자이다.

static long cache[][]

• [i][j]
  • i-1번째 숫자까지 계산했고, 값이 [j]일 때 나머지로 만들 수 있는 경우의 수

static long dp(int index, int value)

현재 index를 처리해야하고, 값이 value일 때, lastNumber를 만들 수 있는 경우의 수

1. 마지막 인덱스까지 처리가 된 경우
   • 만약 lastNumber와 같다면 → 경우의 수 1 추가 → 1 반환
   • 0 반환

2. 캐시값이 이미 존재하는 경우

3. numbers[index]를 value와 더하는 경우
   • 20이 넘으면, 처리하지 않는다.
   • 20 이하라면, 해당 값을 더한다.

4. numbers[index]를 value에서 빼는 경우
   • 0 미만이면, 처리하지 않는다.
   • 0 이상이라면, 해당 값을 뺀다.

---

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class java_5557 {
    static int N;
    static int numbers[];
    static int lastNumber;

    // [i][j] i-1번째 숫자까지 계산했고 값이 [j]일 때 나머지로 만들 수 있는 경우의 수
    static long cache[][];

    // 20이 넘지 않는 음이아닌 정수
    // lastNumber를 만들 수 있는 경우의 수
    static long dp(int index, int value) {
        // 기저사례: 마지막 인덱스까지 처리가 된 경우
        if (index >= numbers.length) {
            if (value == lastNumber) {
                return 1;
            }
            return 0;
        }

        // 기저사례: 캐시값이 이미 존재하는 경우
        if (cache[index][value] != -1) {
            return cache[index][value];
        }

        cache[index][value] = 0;

        // 1. +
        // 더했을 때 20초과면 안된다.
        if (value + numbers[index] <= 20) {
            cache[index][value] += dp(index + 1, value + numbers[index]);
        }

        // 2. -
        // 뺐을 때 0미만이면 안된다.
        if (0 <= value - numbers[index]) {
            cache[index][value] += dp(index + 1, value - numbers[index]);
        }

        return cache[index][value];
    }

    static long solution() {
        // N-1개의 숫자
        // 0~20까지의 값을 가진다.
        cache = new long[N - 1][21];

        // 캐시 초기화
        for (int i = 0; i < cache.length; i++) {
            Arrays.fill(cache[i], -1);
        }

        // 계산
        long result = dp(1, numbers[0]);

        return result;
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        N = Integer.parseInt(br.readLine());
        numbers = new int[N - 1];

        StringTokenizer st = new StringTokenizer(br.readLine());

        for (int i = 0; i < N - 1; i++) {
            numbers[i] = Integer.parseInt(st.nextToken());
        }

        lastNumber = Integer.parseInt(st.nextToken());

        long result = solution();

        System.out.println(result);

        br.close();
    }
}

---

Uploaded by N2T