0910_algorithm_21735_눈덩이굴리기

문제 : https://www.acmicpc.net/problem/21735

초기 구상단계

1. DFS 적용하기 and 재귀호출 사용하기
2. step으로 시간 측정, 종료조건 도달 시 최대값 검사하기
3. 함수 호출 인자 최소로 쓰기
4. case A와 case B를 0과 1로 지정해서 for문으로 돌리기
   case A : 눈덩이 1칸 굴리기
   case B : 눈덩이 2칸 던지기

초기 코드

def dfs(step, idx):
    global maxi
    if step == M:
        if S[-1] >= maxi:
            maxi = S[-1]
            return
    else:
        for i in range(2):
            if i == 0:
                idx += 1
                if idx >= N:
                    idx -= 1
                    continue
                S.append(S[-1] + rail[idx])
                dfs(step + 1, idx)
                S.pop()
                idx -= 1

            else:
                idx += 2
                if idx >= N:
                    idx -= 2
                    continue
                tmp = S[-1] >> 1
                tmp += rail[idx]
                S.append(tmp)
                dfs(step + 1, idx)
                S.pop()
                idx -= 2

S = [1]
maxi = -1
dfs(0, 0)
print(maxi)

• 자꾸만 답이 34로 나와서 debuging.
• 결정적인 문제가 처음 시작이 0부터 시작한다고 생각해놓고 python의 index가 0부터 시작한다는 점을 간과하고 처음 idx값을 0으로 주는 실수를 했다.
• 이 부분 인지하고 dfs(0,-1)로 수정한 후 sample의 값이 28로 잘 나오는 것을 확인하고 제출했지만 틀렸다고 떴다..

최종 코드

def dfs(step, idx):
    global maxi
    if step == M:
        if S[-1] >= maxi:
            maxi = S[-1]
            return
    else:
        for i in range(2):
            if i == 0:
                idx += 1
                if idx >= N:
                    if maxi <= S[-1]:
                        maxi = S[-1]
                    idx -= 1
                    return
                S.append(S[-1] + rail[idx])
                dfs(step + 1, idx)
                S.pop()
                idx -= 1

            else:
                idx += 2
                if idx >= N:
                    if maxi <= S[-1]:
                        maxi = S[-1]
                    idx -= 2
                    return
                tmp = S[-1] >> 1
                tmp += rail[idx]
                S.append(tmp)
                dfs(step + 1, idx)
                S.pop()
                idx -= 2

S = [1]
maxi = -1
dfs(0, -1)
print(maxi)

• 문제가 되는 부분은 바로 idx가 index 범위 밖으로 나가는 경우 그자리에서 끝난다고 명시 되어있는 조건을 간과했다는 것
• 이를 확인하고 if else문에서 있던 idx가 초과하는 경우를 처리하는 코드를 continue에서 최대값 검사한 후 return 시키는 것으로 수정

PASS

더 나아가..

• pass를 받고 나서 다른 사람들의 코드를 봤는데 유독 내 코드가 길다.. 어떻게 된 점인지 확인하고 고민해봐야겠다.