99클럽 코테 스터디 17일차 TIL: 그리디와 애드 혹

오늘의 문제: 31926. 밤양갱

오늘도 보자마자 그리디라는 생각이 들었다. 하지만 문제를 보아하니 실수하기 좋아보여서 어떤 사고 흐름을 가져야 하는지를 명확하게 해야겠다는 생각이 들었다. 사실 이게 애드 혹 문제라는 데 왜 애드 혹인가 처음에는 몰랐더니 단순 계산으로 해결돼서 그런게 아닐까 싶다.

사고의 흐름

1. N = 1 일 때는 daldidal 까지의 코스트 6
2. daldidalgo 까지의 코스트는 8
3. 이후 추가되는 daldidan의 코스트 2
4. 따라서 N = 1일 때의 코스트 10

n=int(input())
def Nparser(n: int):
    i=0
    while n:
        n//=2
        i+=1
    return i
print(Nparser(n)+9)

이후 복사를 해나갈 수 있는 양이 2배씩 커지기 때문에 2의 승수로 어디까지 올라가는지를 체크해서 더해줬다. 사실 약간의 논리의 비약이 있다. 복사하는 양이 커지는 양은 그렇다 치고, 항상 2의 배수가 아닌데 어떻게 똑같나 하는 생각도 든다.

그래서 이 문제가 애드혹으로 분류되지 않나 싶다. 합리적으로 생각해보면 맞는 거 같으면서도 이게 그리디인가 싶은데 분명 번뜩이는 아이디어고.. 괜찮은 문제이긴 한 듯하다. 난이도에 비해서 티어가 조금 높긴 하다.

오늘의 회고

사실 말도 안되는 실수를 해서 한 번 틀리긴 했는데, 그래도 논리의 흐름이 어느 정도 맞았다는 거에서 만족한다. 물론 100% 확실한 근거를 가지고 푼 문제는 아니다만 이정도면 충분한 근거를 가지고 풀었다고 느껴진다.