[TIL] 99클럽 코테 스터디 19일차 TIL + DP

🍀 오늘의 회고

어제와 똑같은 것 같지만, 다른 글이다! ㅎㅎ 오늘도 면접을 보고 왔다. 면접을 보는 날은 하루가 금방 지나가 버리는 것 같다. 이제 알고리즘 스터디와 TIL도 내일이면 끝이다. 벌써 주간 회고를 2주나 밀렸는데, 주말에는 날 잡고 회고를 써야겠다. 기록하지 않고 지나가 버리면 잊어버린다. 한 달 정도 못 봤던 책도 다시 보려고 한다. 다음 주면 독서 라디오 모임이 있는 날인데, AI와 관련된 책이라 얼른 읽어 보고 싶다. 내일 여의도까지 가니까 가는 길에 읽어야겠다.

 

✅ 오늘의 TODO

- 알고리즘

  - 오늘의 문제 ✅

  - Swift 프로그래머스 코딩기초트레이닝 3일 차 🔜

- 면접 ✅

 

🌼 오늘의 문제 - 백준 28069. 김밥천국의 계단

오늘도 바로 DP로 푸는 방법이 떠올랐다. 사실 답에 확신이 없어서 GPT에게 이게 맞는 답이냐고 물어봤는데, 틀릴 수 있다고 했다. 그래도 한 번 제출해 봤는데! 바로 맞았다. 이럴 수가. 그렇지만 BFS로도 풀 수 있다는 사실을 알았다. 다양한 풀이가 가능하다는 사실을 알고 있다고 해도 막상 문제를 보면 바로 떠오르진 않는 것 같다. 다양한 풀이 방법을 보는 습관을 가져야지. 그리고 생각해 보니 점점 복잡도 계산을 안 하고 있었다. 내일부터는 다시 분석하며 공부해야겠다. ^^

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

INF = 9999999
dp = [INF] * (n + 1)
dp[0], dp[1] = 0, 1

for i in range(2, n + 1):
    dp[i] = min(dp[i], dp[i - 1] + 1)
    if i + i // 2 <= n:
        dp[i + i // 2] = dp[i] + 1

if dp[n] <= k:
    print("minigimbob")
else:
    print("water")