오늘은 아프다. 그래도 간절하니까 공부해야지.

1697번 수빈이가 동생 을 몇초 만에 잡을 수 있을까?

뻥 안치고 24시간 만에 풀었다… 원래 1시간 못풀면 검색하기로 스스로 약속했는데 못 지켰다ㅠ_ㅠ 어떻게 풀지 알겠으니까 아까워서 답답해서 더 다른 사람 풀이를 보기가 싫어진다. 처음엔 dfs로 풀다가 0, 100,000 만 넘으면 시간초과, 세그먼테이션폴트(메모리초과)에 메모리제이션, 백트래킹 까지 해봤으나 해결이 되지 않았고(중간에 bfs도 시도함 -> 또 메모리,시간초과) n이 100,000이니까 무조건 선형적인 dp 라는 생각으로 푸니까 풀렸다. 결정적이었던 건 0부터 n까지를 최소값으로 정하면 dp[i//2]를 쓸 수 있겠다라는 아이디어가 생기면서 갑자기 확 풀렸다.

n, k = map(int, input().split())
dp = [float('inf')] * 200002

for i in range(n+1):
    dp[i] = n - i

for i in range(n+1, 100001):
    dp[i] = min(dp[i], i - n)

    if i % 2 == 0 :
        dp[i] = min(dp[i], dp[i//2] + 1, dp[i-1] +1, dp[i+1] +1)
    else:
        dp[i] = min(dp[i], dp[i//2] + 2, dp[i-1] +1, dp[i+1] +1)
    
    #밑에 세줄 주석 처리 하니까 틀림. dp[i] 구해서 갱신해주는게 맞나봐~
    dp[i*2] = min(dp[i*2], dp[i] + 1)
    dp[i+1] = min(dp[i+1], dp[i] + 1)
    dp[i-1] = min(dp[i-1], dp[i] + 1)

print(dp[k])

흐 드디어 다른 사람 풀이 볼 수 있다~ 다른 사람들은 어떻게 풀었을까!? 와… 이게 bfs로 풀리는 문제였구나. 내공 부족이다ㅠ_ㅠ visited가 아니라 array[next] 값이 초기값이면 방문하네… 그래서 나처럼 무한루프가 생기지 않았구나. 나도 이렇게 생각했었는데 depth를 주는걸로 ㅠ_ㅠ 제일 빨리 K 인덱스에 도달하는게 제일 짧은거지! 내껀 바보였어!

def bfs(v):
    q = deque([v])
    while q:
        v = q.popleft()
        if v == k:
            return array[v]
        for next_v in (v-1, v+1, 2*v):
            if 0 <= next_v < MAX and not array[next_v]:
                array[next_v] = array[v] + 1
                q.append(next_v)


MAX = 100001
n, k = map(int, sys.stdin.readline().split())
array = [0] * MAX
print(bfs(n))

내가 짠 bfs는..

def bfs(start):
    visited = [False] * (100001)
    visited[start] = True
    q = deque([(start, 0)])
    
    while q:
        x, cnt = q.popleft()
        print(x , cnt)
        #move = [x, -1, 1]

        if x == k:
            print('why')
            print(cnt)
            return 

        for i in [x-1, x+1, x*2]:
            if 0 <= x + i <= 10000 and visited[x+i] == False:
                visited[x+i] = True
                q.append((i, cnt+1))

bfs(n)

내가 짠 bfs 코드 올바르게 만들어봄. 일단 위에 코드는 max = 100001 이걸 안해서 직접 타이핑 하다보니까 10000 밖에 안하고 곳곳에 코드가 이상함ㅋㅋ 이게 더 빠르네 dp보다. 아 이렇게 짰으면 어제 풀었을텐데 바보야!!!!!!!!!!!!!!!!!!!!!!! 왜ㅠㅠ 지금 보니까 이건 bfs 하라고 낸 문제네. 제일 빨리 그 인덱스에 당도하는 초를 세라고 한거니까;;

from collections import deque

n, k = map(int, input().split())

def bfs(start):
    visited = [False] * (100001)
    visited[start] = True
    q = deque([(start, 0)])
    
    while q:
        x, cnt = q.popleft()

        if x == k:
            print(cnt)
            return 

        for i in [x-1, x+1, x*2]:
            if 0 <= i <= 100000 and visited[i] == False:
                visited[i] = True
                q.append((i, cnt+1))

bfs(n)

역시 dfs 로도 푼 사람이 있군! 이게 제일 시간이 빠름. dfs > bfs > dp 순으로 빠르다. dp로 풀수 있다는 건 dfs로도 가능하다는 말이니까.

def solution(N,K):
    if K <= N: return N-K
    elif K == 1: return 1
    elif K % 2 == 0: return min(K-N,solution(N,K//2)+1)
    else: return min(K-N, solution(N,K+1)+1, solution(N,K-1)+1)
    
N,K = map(int,input().split())
print(solution(N,K))

와 이런 생각은 어떻게 하지?;; 난 포문 돌린걸 이사람은 if K <= N: return N-K 로 간단하게 처리해버렸군 ㄷㄷ 그리고 n -> k 가 아니라 k에서부터 //2로 내려가는 탑다운 방식을 취함. 나는 dfs를 바텀업 방식으로 풀려고 해서 계속 안 풀림ㅠㅠ 저 코드 부분이 없으니까 당연하지… 그래도 모로가도 풀긴했으니까 다행이다. 나처럼 푼 사람 아무도 없나?;; 미친 아무도 없는거보며 이상하게 푼게 맞군 ㅋㅋ

1932번 정수 삼각형에서 가장 아래 층수에 닿는 경로 최대값 구하기

1시간 걸렸나?;; 기억이… 1~2시간 사이인거 같다. 위에 1697번 풀다가 다른 문제 풀고 다시 풀자고 해서 이 문제를 품. 처음엔 dfs로 풀었는데 시간초과가 나서 dfs + dp(메모리제이션) 합쳤는데도 시간초과가 나서 그냥 dp구나 싶어서 dp로 푸니까 그제야 맞았따.

import sys
sys.setrecursionlimit(10**8)

n = int(input())
layer = [list(map(int, sys.stdin.readline().split())) for _ in range(n)]
dp = [[-1 for _ in range(n+1)] for _ in range(n)]
dp[0][0] = layer[0][0]

for floor in range(1, n):
    for i in range(floor+1):
        if i == 0:
            dp[floor][i] = max(dp[floor][i], dp[floor-1][i] + layer[floor][i])
        elif i == floor:
            dp[floor][i] = max(dp[floor][i], dp[floor-1][i-1] + layer[floor][i])
        else:
            dp[floor][i] = max(dp[floor][i], dp[floor-1][i-1] + layer[floor][i], dp[floor-1][i] + layer[floor][i])

print(max(dp[n-1]))

이 코드 이쁘다. 나처럼 dp를 따로 둔게 아니라 layer 리스트 자체의 값을 바꿔 하나의 최대값 루트 경로로 만들었구나! 그리고 한번 밖에 방문을 안해서 나처럼 굳이 0과 floor 인덱스에서는 max로 할 필요도 없다. 그치 맞지…

for i in range(1, N):
    for j in range(i+1):
        if j == 0:
            arr[i][j] += arr[i-1][j]
        elif j == i:
            arr[i][j] += arr[i-1][j-1]
        else:
            arr[i][j] += max(arr[i-1][j-1], arr[i-1][j])


print(max(arr[N-1]))