230904 - [Java-Python] 동적프로그래밍

[robert-min]

풀이 방법 고민

1. 완전탐색 고민 => 탐색할 부분이 많아 시간안에 탐색이 어려움
2. 풀고 싶은 가짜 문제 정의
3. 가짜 문제를 풀면 진짜 문제가 풀리는지 확인
4. 초기값 정의
5. 점화식 구하기
6. 진자 문제 정답 출력

[robert-min]

BOJ.9095 1,2,3 더하기 링크

• 문제풀이
  • 가장 작은 문제 : dp[i]에서 i=4로 했을 때 그보다 작은i로 어떻게 만들어질 지 확인
  • 초기 값: i = 1,2,3은 직접 계산이 가능
  • 점화식 : dp[i] = dp[i-1] + dp[i-2] + dp[i-3]

python

• DP 풀이

  
  import sys
  input = sys.stdin.readline

dp = [0] * (11)

dp[1] = 1 dp[2] = 2 dp[3] = 4

for i in range(4, 11): dp[i] = dp[i-1] + dp[i-2] + dp[i-3]

T = int(input()) for _ in range(T): N = int(input()) print(dp[N])

- 완전 탐색 풀이(DFS)
```python
import sys
input = sys.stdin.readline

def dfs(n):
    global count
    if n == N:
        count += 1
        return

    if n > N:
        return

    dfs(n + 1)
    dfs(n + 2)
    dfs(n + 3)

T = int(input())
for _ in range(T):
    N = int(input())
    count = 0
    dfs(0)
    print(count)

java

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

public class Main {
    static FastReader scan = new FastReader();
    static StringBuilder sb = new StringBuilder();

    static int[] Dy;

    static void preprocess(){
        Dy = new int[15];
        // 초기값 구하기
        Dy[1] = 1;
        Dy[2] = 2;
        Dy[3] = 4;

        // 점화식을 토대로 Dy 배열 채우기
        for (int i = 4; i <= 11; i++){
            Dy[i] = Dy[i - 1] + Dy[i - 2] + Dy[i - 3];
        }
    }

    static void pro() {
        int T = scan.nextInt();
        for (int tt = 1; tt <= T; tt++){
            int N = scan.nextInt();
            sb.append(Dy[N]).append('\n');
        }
        System.out.print(sb);
    }

    public static void main(String[] args) {
        preprocess();
        pro();
    }
}

[robert-min]

BOJ.11725 2*n 타일링 링크

• 문제풀이
  • dp[i]에서 i=2, 3, 4 를 직접 그리면서 점화식 확인

python

import sys
input = sys.stdin.readline

dp = [0] * 1001

dp[1] = 1
dp[2] = 2

for i in range(3, 1001):
    dp[i] = (dp[i-1] + dp[i-2]) % 10007

N = int(input())
print(dp[N])

java

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

public class Main {
    static FastReader scan = new FastReader();
    static StringBuilder sb = new StringBuilder();

    static int N;
    static int[] Dy;

    static void input(){
        N = scan.nextInt();
    }

    static void pro() {
        Dy = new int[1005];
        // 초기값 구하기
        Dy[1] = 1;
        Dy[2] = 2;

        // 점화식을 토대로 Dy 배열 채우기
        for (int i = 3; i <= N; i++){
            Dy[i] = (Dy[i - 1] + Dy[i - 2]) % 10007;
        }
        System.out.println(Dy[N]);
    }

    public static void main(String[] args) {
        input();
        pro();
    }
}

[robert-min]

BOJ.2579 계단 오르기 링크

• 문제풀이
  • 작은문제를 찾기위해 하나씩 표 작성
  • 현재 문제는 연속된 3계단을 밟지 않아야하는 규칙이 있기 때문에 이전 계단을 밟았는지 밟지 않았는지에 따라 DP를 작성
  • 즉, 이전 계단을 밟지 않은 경우 이전전(2칸 전) 계단을 무조건 밟을 것이기 때문에 그 계단이 밟은 경우와 밟지 않은 경우 중 더 큰경우를 선택
  • 이전 계단을 밟은 경우 이전 계단의 전 계단(2칸 전) 계단은 무조건 밟지 않았기 때문에 Dy[i-1][0] + A[i] 만 확인

python

import sys
input = sys.stdin.readline

N = int(input())

from collections import defaultdict
A = defaultdict(int)

for i in range(N):
    A[i] = int(input())

dp = [[0, 0] for _ in range(N+2)]

# init
dp[0][0], dp[0][1] = 0, A[0]

if N >= 2:
    dp[1][0], dp[1][1] = A[1], A[0] + A[1]

for i in range(2, N):
    dp[i][0] = max(dp[i-2][0] + A[i], dp[i-2][1] + A[i])
    dp[i][1] = dp[i-1][0] + A[i]

print(max(dp[N-1][0], dp[N-1][1]))

java

import java.io.*;
import java.util.*;
import java.lang.Math;

public class Main {
    static FastReader scan = new FastReader();
    static StringBuilder sb = new StringBuilder();

    static int N;
    static int[][] Dy;
    static int[] A;

    static void input(){
        N = scan.nextInt();
        A = new int[N + 1];
        Dy = new int[N + 1][2];
        for (int i = 1; i <= N; i++){
            A[i] = scan.nextInt();
        }
    }

    static void pro() {
        // 초기값 구하기
        Dy[1][0] = 0;
        Dy[1][1] = A[1];

        if (N >= 2){
            Dy[2][0] = A[2];
            Dy[2][1] = A[1] + A[2];
        }

        // 점화식을 토대로 Dy 배열 채우기
        for (int i = 3; i <= N; i++){
            Dy[i][0] = Math.max(Dy[i - 2][0] + A[i], Dy[i - 2][1] + A[i]);
            Dy[i][1] = Dy[i - 1][0] + A[i];
        }
        System.out.println(Math.max(Dy[N][0], Dy[N][1]));
    }

    public static void main(String[] args) {
        input();
        pro();
    }
}

[robert-min]

BOJ.11057 오르막 수 링크

• 문제풀이
  • 찾으려는 값이 어떤 값의 연산인지 확인
  • 찾으려는 값은 dp[j][i] = dp[j][i-1] - dp[j-1][i-1] 점화식 확인
  • 초기값 입력하는 부분 확인

python

import sys
input = sys.stdin.readline

N = int(input())

# 1
dp = [[1] * (10) for _ in range(N+1)]

# 2
# # dp[N][0] = sum(dp[N-1])
# dp[1][0] = sum(dp[0])

# # 3
# for i in range(1, 10):
#     dp[1][i] = dp[1][i-1] - dp[0][i-1]

for j in range(1, N+1):
    dp[j][0] = sum(dp[j-1])
    for i in range(1, 10):
        dp[j][i] = dp[j][i-1] - dp[j-1][i-1]

print(sum(dp[N-1]) % 10007)

java

import java.io.*;
import java.util.*;
import java.lang.Math;

public class Main {
    static FastReader scan = new FastReader();
    static StringBuilder sb = new StringBuilder();

    static int N;
    static int[][] Dy;
    static int[] A;

    static void input() {
        N = scan.nextInt();
        A = new int[N + 1];
        Dy = new int[N + 1][10];
    }

    static void pro() {
        // 초기값 구하기
        for (int num = 0; num <= 9; num++) {
            Dy[1][num] = 1;
        }

        // 점화식을 토대로 Dy 배열 채우기
        for (int len = 2; len <= N; len++) {
            for (int num = 0; num <= 9; num++) {
                // 길이가 len이고 num으로 끝나는 개수를 계산하자 == Dy[len][num] 을 계산하자.
                for (int prev = 0; prev <= num; prev++) {
                    Dy[len][num] += Dy[len - 1][prev];
                    Dy[len][num] %= 10007;
                }
            }
        }

        // Dy배열로 정답 계산하기
        int ans = 0;
        for (int num = 0; num <= 9; num++) {
            ans += Dy[N][num];
            ans %= 10007;
        }

        System.out.println(ans);
    }

    public static void main(String[] args) {
        input();
        pro();
    }

}

[robert-min]

BOJ.11066 파일 합치기 링크

[robert-min]

BOJ.15681 트리와 쿼리 링크

• 문제 풀이
  • 일반적으로 dfs + bfs 두번 사용한 풀이는 시간 초과 됨
  • 즉, dfs를 통해 트리를 만들 단계에서 서브 트리 수를 구성하는 dp를 생성해야 함!!
  • 여기서 주의 할 점은 재귀함수 구현 시 setrecursionlimit 설정이 필요

python

• dp 활용 풀이

import sys
sys.setrecursionlimit(100005)
input = sys.stdin.readline

from collections import defaultdict
N, R, Q = map(int, input().split())

graph = defaultdict(list)
for _ in range(N-1):
    u, v = map(int, input().split())

    graph[u].append(v)
    graph[v].append(u)

dp = [0] * (N+1)

def dfs(now, prev):
    global dp
    dp[now] = 1

    for nx in graph[now]:
        if nx == prev: continue
        dfs(nx, now)
        dp[now] += dp[nx]

dfs(R, -1)

for _ in range(Q):
    print(dp[int(input())])

• dfs-bfs 풀이 : 시간초과

  
  import sys
  input = sys.stdin.readline

from collections import defaultdict N, R, Q = map(int, input().split())

graph = defaultdict(list) for _ in range(N-1): u, v = map(int, input().split())

graph[u].append(v)
graph[v].append(u)

from collections import deque

visited = [False] * (N+1) tree = [[] for _ in range(N+1)] def dfs(): Q = deque() Q.append(R) visited[R] = True

while Q:
    now = Q.pop()

    for nx in graph[now]:
        if not visited[nx]:
            visited[nx] = True
            tree[now].append(nx)
            Q.append(nx)

dfs()

def bfs(start): global count Q = deque() Q.append(start)

while Q:
    now = Q.popleft()

    for nx in tree[now]:
        count += 1
        Q.append(nx)

return count

for _ in range(Q): count = 1 query = int(input()) print(bfs(query))

[robert-min]

BOJ.1949 우수 마을 링크

• 문제 풀이
  • dfs 의 특성을 활용해 리프 노드부터 값을 추가
  • dp[i][0] 은 현재 노드에 인원을 추가 하지 않음(다음 노드에서 큰값 사용?)
  • dp[i][1]은 현재 노드의 인원을 추가

python

import sys
sys.setrecursionlimit(100005)
input = sys.stdin.readline

from collections import defaultdict

N = int(input())
town = [0] + list(map(int, input().split()))

graph = defaultdict(list)
for _ in range(N-1):
    u, v = map(int, input().split())
    graph[u].append(v)
    graph[v].append(u)

# dp[i][0] 현재마을X, dp[i][1] 현재마을O
dp = [[0, 0] for _ in range(N+1)]

# 시작마을 1로 가정

def dfs(now, par):
    dp[now][1] = town[now]
    for nx in graph[now]:
        if nx == par: continue
        dfs(nx, now)
        dp[now][0] += max(dp[nx])
        dp[now][1] += dp[nx][0]

dfs(1, -1)

print(max(dp[1]))

[robert-min]

N으로 표현 링크

def solution(N, number):
    if number == 1:
        return 1
    set_list = []

    for cnt in range(1, 9): # 1개부터 8개까지 확인
        partial_set = set()
        partial_set.add(int(str(N) * cnt)) # 이어 붙여서 만드는 경우 넣기
        for i in range(cnt - 1): # (1, n-1) 부터 (n-1, 1)까지 사칙연산
            for op1 in set_list[i]:
                for op2 in set_list[-i - 1]:
                    partial_set.add(op1 + op2)
                    partial_set.add(op1 * op2)
                    partial_set.add(op1 - op2)
                    if op2 != 0:
                        partial_set.add(op1 / op2)
        # 만든 집합에 number가 처음 나오는지 확인
        if number in partial_set:
            return cnt
        set_list.append(partial_set)
    return -1