코테 연습
다이나믹 프로그래밍
첫 번째
https://www.acmicpc.net/problem/22869
22869번: 징검다리 건너기 (small)
$N$개의 돌이 일렬로 나열 되어 있다. $N$개의 돌에는 왼쪽부터 차례대로 수 $A_{1} A_{2} ... A_{i} ... A_{N}$로 부여되어 있다. 가장 왼쪽에 있는 돌에서 출발하여 가장 오른쪽에 있는 돌로 건너가려고
www.acmicpc.net
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번: 쉬운 계단 수
첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다.
www.acmicpc.net
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
첫째 줄에 표의 크기 N과 합을 구해야 하는 횟수 M이 주어진다. (1 ≤ N ≤ 1024, 1 ≤ M ≤ 100,000) 둘째 줄부터 N개의 줄에는 표에 채워져 있는 수가 1행부터 차례대로 주어진다. 다음 M개의 줄에는 네
www.acmicpc.net
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)))
누적합 리스트를 구하는 과정에서 아래 코드가 더 직관적이라는 생각이 든다.
'알고리즘' 카테고리의 다른 글
11.20 알고리즘 문제풀이 (1) | 2023.11.20 |
---|---|
11.19 알고리즘 문제풀이 (0) | 2023.11.19 |
다이나믹 프로그래밍 정리 (0) | 2023.11.16 |
11.16 알고리즘 문제풀이 (1) | 2023.11.16 |
11.15 알고리즘 문제풀이 (0) | 2023.11.15 |