11.15 알고리즘 문제풀이

 

알고리즘 문제풀이

 

다이나믹 프로그래밍

 

스티커

9465번: 스티커

 

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

T = int(input())
arr = []
for _ in range(T):
    n = int(input())
    dp = [list(map(int, input().split())) for _ in range(2)]
    
    if n <= 2:
        if n == 1:
            print(max(dp[0][0], dp[1][0]))
        if n == 2:
            print(max(dp[0][0] + dp[1][1], dp[0][1] + dp[1][0]))
    else:
        dp[0][1] += dp[1][0]
        dp[1][1] += dp[0][0]

        for idx in range(2, n):
            dp[0][idx] += max(dp[1][idx-1], dp[1][idx-2])
            dp[1][idx] += max(dp[0][idx-1], dp[0][idx-2])
        arr.append(max(dp[0][n-1], dp[1][n-1]))
print(*arr, sep="\n")

 

조금 어려웠다.

다이나믹 프로그래밍의 핵심은 문제의 요구사항을 점화식으로 풀어내는 것인데,

점화식으로 풀어내는 것보다 어떻게 하면 구현할지 고민하다가

i+1에서 활용할 수 있는 정보를 i에 저장하도록 구현하려고 했다.

 

지그재그로 진행하는 것 외에도 최대값을 얻을 수 있는 방법이

한 줄 쉬고 바로 다음 줄을 선택하는 방법이 있기 때문에 한 줄 쉬는 겸 전 줄에서의 최대값을 저장하게 시도했다.

필요 이상으로 계산량이 많아지는 것을 느끼고 다시 처음으로 돌아왔다.

 

다이나믹 프로그래밍에는 점화식에 집중하자.

 

점프

1890번: 점프

 

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

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

for r in range(N):
    for c in range(N):
        current_jump = grid[r][c]
        if visit_acc[r][c] == 0 or current_jump == 0:
            continue
                
        nr = r + current_jump
        nc = c + current_jump

        if nc < N:
            visit_acc[r][nc] += visit_acc[r][c]
        if nr < N:
            visit_acc[nr][c] += visit_acc[r][c]
        print(r, c)
        print(*visit_acc, sep="\n")
        print()
print(visit_acc[N-1][N-1])

 

너무 쉬운 문제라서 피드백할 내용이 없다.

다만 시작과 끝의 값에 집중하고 검토할 필요가 있음을 다시 느꼈다.

 

투 포인터

 

배열 합치기

11728번: 배열 합치기

 

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

N, M = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
result = []

a_idx, b_idx = 0, 0
while True:
    if a_idx >= N:
        result.extend(B[b_idx:])
        break
    if b_idx >= M:
        result.extend(A[a_idx:])
        break

    if A[a_idx] >= B[b_idx]:
        result.append(B[b_idx])
        b_idx += 1
        continue
    result.append(A[a_idx])
    a_idx += 1
print(*result, sep=" ")

 

간단하게 정렬로 했어도 풀 수 있는 문제다

최대 N, M이 백만이니깐 2,000,000의 NlogN은 4천2백만 정도 나온다.

실제로 가장 빠르게 푼 답안도 내장된 sorted를 쓰는 답변이다.

나는 투 포인터로 구현했다.

크게 어려운 문제는 아니다.