코테 준비 - DP 2 실버 1 까지

백준 1890 점프

문제

N×N 게임판에 수가 적혀져 있다. 이 게임의 목표는 가장 왼쪽 위 칸에서 가장 오른쪽 아래 칸으로 규칙에 맞게 점프를 해서 가는 것이다.

각 칸에 적혀있는 수는 현재 칸에서 갈 수 있는 거리를 의미한다. 반드시 오른쪽이나 아래쪽으로만 이동해야 한다. 0은 더 이상 진행을 막는 종착점이며, 항상 현재 칸에 적혀있는 수만큼 오른쪽이나 아래로 가야 한다. 한 번 점프를 할 때, 방향을 바꾸면 안 된다. 즉, 한 칸에서 오른쪽으로 점프를 하거나, 아래로 점프를 하는 두 경우만 존재한다.

가장 왼쪽 위 칸에서 가장 오른쪽 아래 칸으로 규칙에 맞게 이동할 수 있는 경로의 개수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 게임 판의 크기 N (4 ≤ N ≤ 100)이 주어진다. 그 다음 N개 줄에는 각 칸에 적혀져 있는 수가 N개씩 주어진다. 칸에 적혀있는 수는 0보다 크거나 같고, 9보다 작거나 같은 정수이며, 가장 오른쪽 아래 칸에는 항상 0이 주어진다.

출력

가장 왼쪽 위 칸에서 가장 오른쪽 아래 칸으로 문제의 규칙에 맞게 갈 수 있는 경로의 개수를 출력한다. 경로의 개수는 263-1보다 작거나 같다.

예제 입력 1 복사

4
2 3 3 1
1 2 1 3
1 2 3 1
3 1 1 0

예제 출력 1 복사

3

오른쪽이나 아래로만 갈 수 있는 점프문제!

경우의 수 구하기!

이것도 결국 트리를 그리겠네요?

어느 지점에 도착했을 때 아래로 가냐 오른쪽으로 가냐니까 거기서 도달하냐 못하냐가 있겠네요

그럼 도착한 것만 생각해서 왼쪽, 위만 생각해서 거꾸로 돌아가기?

거꾸로 말고 그냥 정 방향으로 가는게 정신적으로 깔끔하겠네요 ...

import sys
input = sys.stdin.readline
n = int(input())
num = [list(map(int,input().split())) for _ in range(n)]
dt = [[0]*n for _ in range(n)]

dt[0][0] = 1

for i in range(n):
    for j in range(n):
        if(dt[i][j]==0 or num[i][j]== 0):
            continue
        if(num[i][j]+j<n):
            dt[i][j+num[i][j]]+=dt[i][j]
        if(num[i][j]+i<n):
            dt[i+num[i][j]][j]+=dt[i][j]

print(dt[n-1][n-1])

구현도 너무 오랜만에 하니까 자꾸 오타도 나고 이상하게도 가네요...ㅜ

 

백준 15645 내려가기 2

예제 입력 1

3
1 2 3
4 5 6
4 9 0

예제 출력 1

18 6

음 이것도 최대, 최소 문제네요

양 끝은 2가지만 가능하고, 중간에 있는 숫자들은 3가지 경우의 수가 있네요.

저는 끝에서 부터 하는게 항상 편해서 뒤에서 시작할게요....

import sys
input = sys.stdin.readline
n = int(input())
num = [list(map(int,input().split())) for _ in range(n)]
dt = [[0]*n for _ in range(n)]

for i in range (n):
    dt[n-1][i]= num[n-1][i]

for i in range(n - 2, -1, -1):
    for j in range (n):
        if(j==0):
            dt[i][0]=num[i][0] +max(dt[i+1][0],dt[i+1][1])
            continue
        if (j==n-1):
            dt[i][j]=num[i][j] +max(dt[i+1][j],dt[i+1][j-1])
            continue
        dt[i][j]=num[i][j] +max(dt[i+1][j],dt[i+1][j-1],dt[i+1][j+1])

a = dt[0][0]
for i in range (n):
    a = max(dt[0][i],a)
dt = [[0]*n for _ in range(n)]

for i in range(n - 2, -1, -1):
    for j in range (n):
        if(j==0):
            dt[i][0]=num[i][0] +min(dt[i+1][0],dt[i+1][1])
            continue
        if (j==n-1):
            dt[i][j]=num[i][j] +min(dt[i+1][j],dt[i+1][j-1])
            continue
        dt[i][j]=num[i][j] +min(dt[i+1][j],dt[i+1][j-1],dt[i+1][j+1])
        
b = dt[0][0]
for i in range (n):
    b = min(dt[0][i],b)

print(a,b)

 메모리가 터져버렸습니다.

n이 10만까지였네요....

굳이 모든 열을 다 저장하지 말고, 한줄씩만 저장해서 넘기면 되네요...

import sys
input = sys.stdin.readline

dp = []
for _ in range(N):
    dp.append(tuple(map(int, input().split())))

 이 형식의 입력에 익숙해져야겠네요

아 그리고 n*n이 아니라 n*3이네요....?

앗....

 

백준 1149 RGB거리

RGB거리에는 집이 N개 있다. 거리는 선분으로 나타낼 수 있고, 1번 집부터 N번 집이 순서대로 있다.

집은 빨강, 초록, 파랑 중 하나의 색으로 칠해야 한다. 각각의 집을 빨강, 초록, 파랑으로 칠하는 비용이 주어졌을 때, 아래 규칙을 만족하면서 모든 집을 칠하는 비용의 최솟값을 구해보자.

• 1번 집의 색은 2번 집의 색과 같지 않아야 한다.
• N번 집의 색은 N-1번 집의 색과 같지 않아야 한다.
• i(2 ≤ i ≤ N-1)번 집의 색은 i-1번, i+1번 집의 색과 같지 않아야 한다.

입력

첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 같은 자연수이다.

출력

첫째 줄에 모든 집을 칠하는 비용의 최솟값을 출력한다.

예제 입력 1 복사

3
26 40 83
49 60 57
13 89 99

예제 출력 1 복사

96

예제 입력 2 복사

3
1 100 100
100 1 100
100 100 1

예제 출력 2 복사

3

예제 입력 3 복사

3
1 100 100
100 100 100
1 100 100

예제 출력 3 복사

102

예제 입력 4 복사

6
30 19 5
64 77 64
15 19 97
4 71 57
90 86 84
93 32 91

예제 출력 4 복사

208

예제 입력 5 복사

8
71 39 44
32 83 55
51 37 63
89 29 100
83 58 11
65 13 15
47 25 29
60 66 19

예제 출력 5 복사

253

1 ~ N 까지의 집이 있는데 1,2 번의 집 색이 구해지면 나머지 집의 색도 정해지네요

why? 빨 -> 파 -> 초 -> 빨 ->파 -> 초 .....

그럼 6개의 경우의 수가 있으니까 다 더하면서 저장하기?

아 문제를 잘못 이해했네요 3개가 같으면 안되는게 아니라 그냥 기준 좌우로 같으면 안되는거였네요

 

 제발 네ㅣㅇ버............................................................

문제 잘 읽기

 

백준 9465 스티커

입력

첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 n (1 ≤ n ≤ 100,000)이 주어진다. 다음 두 줄에는 n개의 정수가 주어지며, 각 정수는 그 위치에 해당하는 스티커의 점수이다. 연속하는 두 정수 사이에는 빈 칸이 하나 있다. 점수는 0보다 크거나 같고, 100보다 작거나 같은 정수이다. 

출력

각 테스트 케이스 마다, 2n개의 스티커 중에서 두 변을 공유하지 않는 스티커 점수의 최댓값을 출력한다.

예제 입력 1 

2
5
50 10 100 20 40
30 50 70 10 60
7
10 30 10 50 100 20 40
20 40 30 50 60 20 80

예제 출력 1 

260
290

스티커를 때면 광역딜을 맥인다!!

최대한 비싼것만 살리자!

그럼 기회비용을 다 맥인 다음에 기회비용 적은 것 찾기...?

이것도 결국 모든 경우의 수를 다 구하는데, 대각선으로 갈 때 한칸만 가냐, 두칸 전부를 가냐 이렇게 결정하면 된다. 

 

백준 11053 가장 긴 증가하는 부분

문제

수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오.

예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이다.

입력

첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000)이 주어진다.

둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000)

출력

첫째 줄에 수열 A의 가장 긴 증가하는 부분 수열의 길이를 출력한다.

예제 입력 1 복사

6
10 20 10 30 20 50

예제 출력 1 복사

4

그럼 중복을 다 빼고, 다른 숫자의 개수만 세면 되는 문제인데 최소부터 하나씩 다 찾기엔 n^2 복잡도가 나온다. 그렇게 푸는 문제가 아닌거 같은데

그럼 백터를 두개 만들고 있는 숫자만 1을 입력해서 sum하기!

문제를 잘못 안건가...?

n = int(input().strip())
a = list(map(int, input().strip().split()))

# dp[i]는 i번째 수를 마지막으로 하는 가장 긴 증가하는 부분 수열의 길이
dp = [1] * n  # 각 위치에 대해 최소 길이는 1

for i in range(1, n):
    for j in range(i):
        if a[j] < a[i]:
            dp[i] = max(dp[i], dp[j] + 1)

# dp 배열 중 최댓값이 가장 긴 증가하는 부분 수열의 길이
print(max(dp))

아 내 맘대로 배열하면 안되는 거였군요.....ㅠ