11.18 알고리즘 문제풀이

코테 연습

 

다이나믹 프로그래밍

 

첫 번째

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

22869번: 징검다리 건너기 (small)

import sys
input = lambda: sys.stdin.readline().rstrip()

N, K = map(int, input().split())
A = list(map(int, input().split()))

dp = [False] * N
dp[0] = True

for idx in range(N):
        for next in range(idx+1, N):
            if dp[idx] and (next-idx) * (1+abs(A[next]-A[idx])) <= K:
                dp[next] = True
print("YES" if dp[-1] else "NO")

import sys
input = sys.stdin.readline

N, K = map(int, input().split())
A = list(map(int, input().split()))
dp = [1] + [0]*(N-1)

for i in range(1, N):
    for j in range(i-1, max(0, i-K)-1, -1):
        if dp[j] and ((i-j)*(1+abs(A[i]-A[j])) <= K):
            dp[i] = 1
            break

print('YES' if dp[N-1] else 'NO')

 

비슷해 보이는 두 코드의 실행 속도는 꽤 차이가 난다.

위에 있는 코드는 내가 작성한 코드이고 아래 코드는 현재 기준으로 가장 짧은 실행 시간을 가진 코드이다.

(next-idx) * (1+abs(A[next]-A[idx])) <= K

위 계산을 꼭 필요한 상태에서만 실행되도록 한 것이 차이를 만들었다고 생각한다.

 

두 번째

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

10844번: 쉬운 계단 수

import sys
input = lambda: sys.stdin.readline().rstrip()

N = int(input())
stair = [[0] + [1 for _ in range(1, 10)]] + [[0 for _ in range(10)] for _ in range(N-1)]

for i in range(1, N):
    for j in range(10):
        if j-1 >= 0:
            stair[i][j] += stair[i-1][j-1]
        if j+1 < 10:
            stair[i][j] += stair[i-1][j+1]
print(sum(stair[-1]) % 1000000000)

dp 테이블의 원소에 리스트를 저장하는, 색다른 문제였다고 생각한다.

 

세 번째

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

11660번: 구간 합 구하기 5

 

import sys
input = lambda: sys.stdin.readline().rstrip()

N, M = map(int, input().split())
grid = [[0 for _ in range(N+1)]] + [[0] + list(map(int, input().split())) for _ in range(N)]
test = [list(map(int, input().split())) for _ in range(M)]

sum_grid = [[0] * (N+1) for _ in range(N+1)]
sum_grid[1][1] = grid[1][1]
for c in range(2, N+1):
    sum_grid[1][c] = sum_grid[1][c-1] + grid[1][c]
for r in range(2, N+1):
    sum_grid[r][1] = sum_grid[r-1][1] + grid[r][1]
for r in range(2, N+1):
    for c in range(2, N+1):
        sum_grid[r][c] = sum_grid[r][c-1] + sum_grid[r-1][c] - sum_grid[r-1][c-1] + grid[r][c]

for t in test:
    x1, y1, x2, y2 = t
    print(sum_grid[x2][y2] - sum_grid[x1-1][y2] - sum_grid[x2][y1-1] + sum_grid[x1-1][y1-1])

import os, io, sys
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline

N, M = map(int, input().split())
arr = [[0] * (N + 1)] + [[0] + list(map(int, input().split())) for _ in range(N)]
ans = []

for y in range(1, N + 1):
	for x in range(2, N + 1):
		arr[y][x] += arr[y][x - 1]

for x in range(1, N + 1):
	for y in range(2, N + 1):
		arr[y][x] += arr[y - 1][x]

for _ in range(M):
	x1, y1, x2, y2 = map(int, input().split())
	ans.append(arr[x2][y2] - arr[x1 - 1][y2] - arr[x2][y1 - 1] + arr[x1 - 1][y1 - 1])

sys.stdout.write('\n'.join(map(str, ans)))

 

누적합 리스트를 구하는 과정에서 아래 코드가 더 직관적이라는 생각이 든다.