시나공

시험에

나오는 것만

공부한다!

안녕하세요.

240p 알고리즘의 이해에서와 같이 사과의 개수를 1021이라고 한다면(문제의 조건을 만족하는 값이 1021입니다.)

J = 1021, K = 1

첫 번째 사람(A)이 사과를 4등분(255,255,255,255) 하고 나머지를 계산합니다.

NMG는 1

4등분하고 남은 1개를 먹어야 하므로 J = J - 1, J는 1020

배열의 위치 증가 N = N + 1, N은 1

4등분 중 한 몫을 첫 번째 사람(A)이 가져가므로 A(1)은 255

4등분 한 것에서 한 사람의 몫을 가져갔으니 그 값을 빼야 하므로 J = J * 3 /4 (한 사람의 몫이 1/4이므로)

J = (1020 * 3) / 4 = 765

J = 765, K = 2

첫 번째 사람(B)이 사과를 4등분(191,191,191,191) 하고 나머지를 계산합니다.

NMG는 1

4등분하고 남은 1개를 먹어야 하므로 J = J - 1, J는 764

배열의 위치 증가 N = N + 1, N은 2

4등분 중 한 몫을 두 번째 사람(B)이 가져가므로 A(2)은 191

4등분 한 것에서 한 사람의 몫을 가져갔으니 그 값을 빼야 하므로 J = J * 3 /4 (한 사람의 몫이 1/4이므로)

J = (764 * 3) / 4 = 573

J = 573, K = 3

첫 번째 사람(C)이 사과를 4등분(143,143,143,143) 하고 나머지를 계산합니다.

NMG는 1

4등분하고 남은 1개를 먹어야 하므로 J = J - 1, J는 572

배열의 위치 증가 N = N + 1, N은 3

4등분 중 한 몫을 세 번째 사람(C)이 가져가므로 A(3)은 143

4등분 한 것에서 한 사람의 몫을 가져갔으니 그 값을 빼야 하므로 J = J * 3 /4 (한 사람의 몫이 1/4이므로)

J = (573 * 3) / 4 = 429

J = 429, K = 4

첫 번째 사람(D)이 사과를 4등분(107,107,107,107) 하고 나머지를 계산합니다.

NMG는 1

4등분하고 남은 1개를 먹어야 하므로 J = J - 1, J는 428

배열의 위치 증가 N = N + 1, N은 4

4등분 중 한 몫을 네 번째 사람(D)이 가져가므로 A(4)은 107

4등분 한 것에서 한 사람의 몫을 가져갔으니 그 값을 빼야 하므로 J = J * 3 /4 (한 사람의 몫이 1/4이므로)

J = (428 * 3) / 4 = 321

문제의 조건에 마지막 D가 자기 몫을 가지고 간 후 나머지를 4등분해 보아 나머지가 1인지도 확인해 봐야 하므로

인원은 4명이지만 위 작업은 5번을 반복해야 합니다. 그래서 K < 5 때까지 반복하는 것이죠

그래서 한 번 더 반복하면

J = 321, K = 5

확인 반복을 위해 사과를 4등분(80,80,80,80) 하고 나머지를 계산합니다.

NMG는 1, 나머지가 1인지 확인이 되었지만 반복 과정에서의 작업은 그대로 이어서 수행합니다.

4등분하고 남은 1개를 먹어야 하므로 J = J - 1, J는 320

배열의 위치 증가 N = N + 1, N은 5

4등분 중 한 몫을 다섯 번째 배열에 넣으므로 A(5)는 80

4등분 한 것에서 한 사람의 몫을 가져갔으니 그 값을 빼야 하므로 J = J * 3 /4 (한 사람의 몫이 1/4이므로)

J = (320 * 3) / 4 = 240

이제 K가 5보다 작지 않으므로 아래쪽으로 내려와

NMG = J + A(5) + 1을 계산합니다.

이는 4명이 가져간 후 남은 사과도 조건에 만족하는지 처리한 다섯 번째 과정을 복귀하는 것으로

J는 다섯 번째 과정에서 얻은 240

A(5)는 다섯 번째 과정에서 챙긴 한 사람 몫 80

그리고 +1은 남은 1개를 먹은 것 1

그래서 NMG는 240+80+1 = 321이 됩니다.

즉 다섯 번째를 반복하기 전 J 값이 되는 것이죠.

하지만 확인을 위해 다섯 번째 작업을 수행하였으므로 확인이 완료된 후 그 전 값으로 복귀하는 과정을 수행한 것입니다.

오늘도 즐거운 하루 되세요.