자유 게시판 / Forum

혹시 과제 8번 푸신분...

by ciment1010, 10월 17일, 03:07

prof , 10월 17일, 10:10
 누구나다 그런 경험이 있습니다. 이렇게 악착같이 해보는 사람들이 결국은 성공합니다.
힌트는 회전판으로 구성된 자물쇠... 돌려서 번호 맞추는 자물쇠 있잖아요,
자전거 잠글 때 쓰는 것...

그걸 stack으로 만들어서 돌리면 됩니다. 시간이 3초라 대부분 해결됩니다.

변수 갯수만큼 stack 크기를 정합니다.
옆으로 뉘어보께요.
변수가 4개라고 해 봅시다. 그러면 일단 1 1 1 1 1부터 시작합니다.

[ 1 1 1 1] 이게 답은 아니겠죠? 그러면 제일 오른쪽, stack top을 하나 증가시킵니다.

[1 1 1 2 ]
쭉 쭉,....

결국언젠가 top 이 끝에 도달합니다.
[ 1 1 1 50] 이 끝입니다. 끝이므로 top을 꺼냅니다.

[ 1 1 1  ? ]

다음 단계는
[ 1 1 2 ? ]
입ㄴ다. 그러면 제일 오른쪽 숫자는 뭐가 되어야 할까요 ?
그렇지요. 다시 1이죠.

 stack에 들어갈 때는 항상 제일 처음 숫자로 들어갑니다.
다시

[1 1 2 1 ] 에서 쭉쭉갑니다. [ 1 1 2 K]에 끝입니다. 그러면 다시 K를 꺼내고
stack을 봅니다.

stack top이 2죠 ?  2 다음 가능한 원소가 있나요 ? 예 있습니다. 3이죠

[ 1 1 3 ? ]이 되고 [ 1 1 3 1]에서 또 돌립니다. 

세월이 흘러흘러

[1 1 20 K]까지 왔습니다. K가 끝이므로pop

[1 1 20 ?]  다시 top=20이 끝이므로 pop

[ 1 1 ? ? ] 에서 next가 가능하죠 ?

[ 1 2 ?? ] 입니다. 아까 뽑힌 것 다시 다 쳐 넣습니다. 어떻게?
stack에 들어갈 떄는 항상 처음부터 들어갑니다.

[1 2 1 1] 또 달립니다. 언제까지 ?

[K ? ? ? ] 제일 바닥에 있는 원소가 끝일때까지...

먼저 손으로 해보세요.  "손"이 먼저 이해가 되어야 합니다. 
ciment1010 , 10월 17일, 03:09
 (바로 엔터를 눌러서 글 내용을 못썼네요ㅠㅠ)
혹시 8번 푸신 분 푸는데 시간 얼마나 걸리셨나요...
저는 3일째하고 있는데 어떻게 해야할 지 손도 못대고 있네요...눈물이 납니다 진짜ㅠㅠ