[자바]백준 13699번 점화식[다이나믹 프로그래밍][엄탱]

안녕하세요. 개발자 엄탱입니다.
이 글은 알고리즘을 공부하면서 공부 기록용입니다.
그래서 설명마다 일기용으로 편하게 작성하여 반말 형식으로 작성하려고 합니다.
그리고 보시다가 더 좋은 방법이나 잘 못 알고 있는 내용이 있다면 알려주시면 정말 감사하겠습니다.
좋은 하루 되세요 :)

문제 링크

https://tang25.tistory.com/48

[자바]백준 14916번 거스름돈[다이나믹프로그래밍][엄탱]

문제 설명

문제는 이해하기 어렵지 않다.

수열 t(n)을 구하는 것인데 t(n)의 점화식 규칙대로 값을 구하는 것이다.

규칙은 아래와 같다.

• t(n) = t(0) * t(n-1) + t(1) * t(n-2) +...+t (n-1) * t(0)

해설

위의 수열 t(n) 규칙을 보면 반복된 값이 있다.

또한, 규칙 안에서의 또 다른 값들 t(n - 1), t(n - 2)... 값들을 구하려면 또 저 규칙대로 반복문을 돌리고 또 그 안에서 반복문을 돌리고 그러다 보면 시간 오버가 된다.

 

이 문제는 대표적인 dp 문제중 하나라고 생각 든다.

반복된 값을 기록해 나가면서 또 다시 해당 값을 구하는 과정을 생략해 주는 게 핵심이다.

t(0)부터 t(n)까지 순서대로 구하면서 구하는 과정에서 기존에 구해준 값들을 사용하면서 구해주면 된다. 

 

코드를 살펴 보겠습니당

코드 1

import java.io.BufferedReader;
import java.io.InputStreamReader;

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

        int n = Integer.parseInt(br.readLine());
        
        long[] t = new long[n + 2];
        
        t[0] = 1;
        t[1] = 1;
        
        for (int i = 2; i <= n; i++) {
            for (int j = 0; j < i; j++) {
                t[i] += t[j] * t[i - 1 - j];
            }
        }

        System.out.println(t[n]);
        br.close();
    }
}

코드 2는 코드 1보다 좀 더 시간을 단축시킨 코드인데, 내가 거쳐온 존경하는 시니어분들(단 두 분뿐이지만..)이 하시는 말씀이 있는데 그분들이 하신 말씀 중에 '느껴지지도 않는 성능을 위해 코드를 복잡하게 짜는 것보다 읽기 쉬운 코드가 훨씬 좋다. 성능은 문제가 생긴 후에 코드를 수정해도 괜찮다'는 말씀들을 하셨다.

그래서 위에 코드가 훨씬 좋다고 생각한다.

 

코드 2

import java.io.BufferedReader;
import java.io.InputStreamReader;

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

        int n = Integer.parseInt(br.readLine());
        
        long[] t = new long[n + 2];
        
        t[0] = 1;
        t[1] = 1;
        
        for (int i = 2; i <= n; i++) {
            for (int j = 0; j < i / 2 + i % 2; j++) {
                t[i] += t[j] * t[i - 1 - j];
                
                if (j != i - 1 - j) {
                    t[i] += t[j] * t[i - 1 - j];
                }
            }
        }

        System.out.println(t[n]);
        br.close();
    }
}