22251번 - 빌런 호석
제가 시작하자마자 틀린 원인 두 가지 공유드립니다.
1) 0층도 정답 개수로 포함 시킴.
-> 아무 생각 없이 코딩 하면 틀림
2) 한 층씩 값을 바꿀 때, back tracking 을 너무 빠르게 하지 말기.
-> 저의 경우 dfs로 풀이 진행하며 현재까지 바꾼 층이 N보다 크면 return 시켰었는데, 그럴 경우 fail이 발생하게 됩니다.
ex) N = 131 , 현재 값 = 142 , 현재 바꿀 자리수 = 10의 자리
위의 조건 일 경우 현재 값은 132가 될 수 있고, 이후 1의 자리를 변화 시킬 때 130이 될 수 있으므로 142를 정답 개수에 포함시키는 않지만 바꾸는 연산은 진행해 보아야 합니다.
그 이후 1의 자리를 바꾸려고 할 때, 현재 바꿀 자리보다 앞의 자리가 N[앞의 자리] 값 보다 클 경우에는 항상 N보다 크므로 return 시켜버리면 됩니다.
ex) N = 131, 현재 값 = 141, 현재 바꿀 자리수 = 1의 자리 -> 어떻게 해도 N보다 커짐
댓글을 작성하려면 로그인해야 합니다.
gytkd33 1년 전
제가 시작하자마자 틀린 원인 두 가지 공유드립니다.
1) 0층도 정답 개수로 포함 시킴.
-> 아무 생각 없이 코딩 하면 틀림
2) 한 층씩 값을 바꿀 때, back tracking 을 너무 빠르게 하지 말기.
-> 저의 경우 dfs로 풀이 진행하며 현재까지 바꾼 층이 N보다 크면 return 시켰었는데, 그럴 경우 fail이 발생하게 됩니다.
ex) N = 131 , 현재 값 = 142 , 현재 바꿀 자리수 = 10의 자리
위의 조건 일 경우 현재 값은 132가 될 수 있고, 이후 1의 자리를 변화 시킬 때 130이 될 수 있으므로 142를 정답 개수에 포함시키는 않지만 바꾸는 연산은 진행해 보아야 합니다.
그 이후 1의 자리를 바꾸려고 할 때, 현재 바꿀 자리보다 앞의 자리가 N[앞의 자리] 값 보다 클 경우에는 항상 N보다 크므로 return 시켜버리면 됩니다.
ex) N = 131, 현재 값 = 141, 현재 바꿀 자리수 = 1의 자리 -> 어떻게 해도 N보다 커짐