12094번 - 2048 (Hard)
파이썬으로는 일반적으로 흔히 알려진 방법(C++)으로 해결할 수 없습니다. 때문에 풀이법을 까먹은 미래의 나와 앞으로 이 문제를 접할 파이썬 유저 분들을 위해 기록해둡니다.
1. 흔히 알려진 2가지 가지치기 방식중 '합친후 변화가 있는지 없는지 확인'하는 가지치기와 '나머지 한가지 가지치기 방식을 심화'한 방법이 필요합니다.
2. import copy를 사용하지 않으면 시간단축 가능하다고 해서 슬라이드로 구현했습니다. (체감효과 O)
3. 해결방법의 핵심은 메모를 최고깊이 만큼을 선언후 깊이(depth,cnt)에서 도달할수 있는 최고값을 기록하는 방식입니다. (예시: (memo = [0] * 11))
3.1 최고값 기록하는법은 최고깊이에 도달할 경우 다음과 같은 방식으로 진행합니다.
if 최고깊이에 도달: temp = 현재 최고값 if 본래 최고값 < 현재 최고값(temp): 본래 최고값 = 현재 최고값(temp) for i in range(최고깊이, -1, -1): memo[i] = temp temp // 2
3.2 보충 설명을 하자면 현재깊이의 최고값과 이전깊이 최고값의 차이는 딱 절반만큼 차이나이때문에 이를 미리 메모하여 깊게 들어가는것을 방지합니다.(예를들자면 깊이가 10일때 최고값이 1024라면 깊이가 9면 512, 8이면 256, 7이면 128... 이런식이 됩니다.)
3.3 나머지는 흔히 알려진 방식대로 그래프의 모든값중 memo[현재깊이]보다 큰값이 존재하면 계속 진행하고 그렇지 않다면 더 이상 깊게 들어가지 않게끔 작성합니다.
4. 합치는 방법은 돌리는방법 혹은 (up,down,left,right)를 일일히 구현하는 방법 12100 2048(easy)에서 사용했던 방법 그대로 가져오셔도 상관없습니다.
질문판에 올라왔던 반례입니다.2064 64 32 16 256 0 32 0 512 0 0 128 0 0 0 128 16 64 16 016 16 64 0 0 128 64 0 0 0 8 0 256 0 512 128 32 0 16 320 128 0 0 0 32 32 64 0 0 0 0 0 32 16 64 0 16 0 00 0 0 128 0 128 512 0 0 32 256 32 64 0 32 0 64 0 0 00 0 0 16 0 16 0 0 32 0 32 0 0 0 64 0 64 64 0 6416 0 64 32 128 64 0 128 16 0 0 0 64 0 0 128 0 64 0 1280 64 32 64 64 0 0 0 128 0 0 0 512 32 0 64 0 0 64 00 0 0 0 0 8 256 0 0 32 0 0 0 0 0 8 128 16 0 640 8 0 16 0 0 0 128 0 16 16 0 32 0 0 0 0 64 128 1280 16 16 32 64 0 64 256 0 16 128 128 0 0 64 0 16 0 0 00 0 0 16 0 0 0 0 32 0 8 16 128 64 256 0 32 16 128 00 256 16 256 0 16 32 8 128 64 0 32 32 512 0 16 0 8 16 064 8 16 0 0 0 0 0 128 64 0 128 0 0 8 0 16 0 0 00 0 0 0 32 64 0 8 0 0 32 0 0 0 16 128 256 0 128 064 8 0 16 32 0 0 0 8 64 64 0 0 0 0 256 64 0 16 00 0 32 0 32 32 8 0 0 0 64 0 32 0 0 16 64 128 0 320 0 8 64 0 64 0 0 128 64 64 0 0 0 0 32 128 0 128 160 0 0 0 32 0 0 32 32 0 16 0 128 0 0 0 0 256 0 3216 256 0 64 0 16 0 64 0 32 64 32 0 0 0 64 32 64 0 016 8 0 32 64 256 0 0 0 128 8 0 32 0 64 0 0 0 64 128
댓글을 작성하려면 로그인해야 합니다.
taeyang95 3년 전 5
파이썬으로는 일반적으로 흔히 알려진 방법(C++)으로 해결할 수 없습니다.
때문에 풀이법을 까먹은 미래의 나와 앞으로 이 문제를 접할 파이썬 유저 분들을 위해 기록해둡니다.
1. 흔히 알려진 2가지 가지치기 방식중 '합친후 변화가 있는지 없는지 확인'하는 가지치기와 '나머지 한가지 가지치기 방식을 심화'한 방법이 필요합니다.
2. import copy를 사용하지 않으면 시간단축 가능하다고 해서 슬라이드로 구현했습니다. (체감효과 O)
3. 해결방법의 핵심은 메모를 최고깊이 만큼을 선언후 깊이(depth,cnt)에서 도달할수 있는 최고값을 기록하는 방식입니다.
(예시: (memo = [0] * 11))
3.1 최고값 기록하는법은 최고깊이에 도달할 경우 다음과 같은 방식으로 진행합니다.
if 최고깊이에 도달: temp = 현재 최고값 if 본래 최고값 < 현재 최고값(temp): 본래 최고값 = 현재 최고값(temp) for i in range(최고깊이, -1, -1): memo[i] = temp temp // 23.2 보충 설명을 하자면 현재깊이의 최고값과 이전깊이 최고값의 차이는 딱 절반만큼 차이나이때문에 이를 미리 메모하여 깊게 들어가는것을 방지합니다.
(예를들자면 깊이가 10일때 최고값이 1024라면 깊이가 9면 512, 8이면 256, 7이면 128... 이런식이 됩니다.)
3.3 나머지는 흔히 알려진 방식대로 그래프의 모든값중 memo[현재깊이]보다 큰값이 존재하면 계속 진행하고 그렇지 않다면 더 이상 깊게 들어가지 않게끔 작성합니다.
4. 합치는 방법은 돌리는방법 혹은 (up,down,left,right)를 일일히 구현하는 방법 12100 2048(easy)에서 사용했던 방법 그대로 가져오셔도 상관없습니다.
질문판에 올라왔던 반례입니다.
20
64 64 32 16 256 0 32 0 512 0 0 128 0 0 0 128 16 64 16 0
16 16 64 0 0 128 64 0 0 0 8 0 256 0 512 128 32 0 16 32
0 128 0 0 0 32 32 64 0 0 0 0 0 32 16 64 0 16 0 0
0 0 0 128 0 128 512 0 0 32 256 32 64 0 32 0 64 0 0 0
0 0 0 16 0 16 0 0 32 0 32 0 0 0 64 0 64 64 0 64
16 0 64 32 128 64 0 128 16 0 0 0 64 0 0 128 0 64 0 128
0 64 32 64 64 0 0 0 128 0 0 0 512 32 0 64 0 0 64 0
0 0 0 0 0 8 256 0 0 32 0 0 0 0 0 8 128 16 0 64
0 8 0 16 0 0 0 128 0 16 16 0 32 0 0 0 0 64 128 128
0 16 16 32 64 0 64 256 0 16 128 128 0 0 64 0 16 0 0 0
0 0 0 16 0 0 0 0 32 0 8 16 128 64 256 0 32 16 128 0
0 256 16 256 0 16 32 8 128 64 0 32 32 512 0 16 0 8 16 0
64 8 16 0 0 0 0 0 128 64 0 128 0 0 8 0 16 0 0 0
0 0 0 0 32 64 0 8 0 0 32 0 0 0 16 128 256 0 128 0
64 8 0 16 32 0 0 0 8 64 64 0 0 0 0 256 64 0 16 0
0 0 32 0 32 32 8 0 0 0 64 0 32 0 0 16 64 128 0 32
0 0 8 64 0 64 0 0 128 64 64 0 0 0 0 32 128 0 128 16
0 0 0 0 32 0 0 32 32 0 16 0 128 0 0 0 0 256 0 32
16 256 0 64 0 16 0 64 0 32 64 32 0 0 0 64 32 64 0 0
16 8 0 32 64 256 0 0 0 128 8 0 32 0 64 0 0 0 64 128