Maintenance script: Table transclusion repair v1

2026-03-27T12:46:19Z

Table transclusion repair v1

← Older revision		Revision as of 12:46, 27 March 2026
Line 7:		Line 7:
	[http://online-judge.uva.es/p/v102/p10254b.jpg]		[http://online-judge.uva.es/p/v102/p10254b.jpg]
	사원에 있는 수도사 중 한 명이 동료 수도사에게 침을 하나만 추가하면 1초에 원반을 하나씩 옮긴다고 할 때 한 나절이면 모든 원반을 옮길 수 있을 것이라고 알려주었다. 그가 제안한 방법은 다음과 같다.		사원에 있는 수도사 중 한 명이 동료 수도사에게 침을 하나만 추가하면 1초에 원반을 하나씩 옮긴다고 할 때 한 나절이면 모든 원반을 옮길 수 있을 것이라고 알려주었다. 그가 제안한 방법은 다음과 같다.
	~~{{\|~~
	# 맨 위에 있는 원반(맨 위에 있는 k개의 원반)을 다른 침으로 옮긴다.		# 맨 위에 있는 원반(맨 위에 있는 k개의 원반)을 다른 침으로 옮긴다.
	# 침이 세 개 있는 경우에 쓰는 방법을 그대로 적용해서 나머지 n-k개의 원반(전체 원반의 개수를 n개라고 가정)을 목표 지점으로 옮긴다.		# 침이 세 개 있는 경우에 쓰는 방법을 그대로 적용해서 나머지 n-k개의 원반(전체 원반의 개수를 n개라고 가정)을 목표 지점으로 옮긴다.
	# 마지막으로 네 개의 침을 이용해서 맨 위에 있던 k개의 원반을 최종 목적지로 옮긴다.		# 마지막으로 네 개의 침을 이용해서 맨 위에 있던 k개의 원반을 최종 목적지로 옮긴다.
	~~\|}}~~
	이동 횟수를 최소화할 수 있는 k값을 계산한 다음 18,433번만 옮기면 된다는 결론을 내렸다. 따라서 침이 세 개만 있을 때는 5천억년이 걸릴 일을 침 하나만 추가하면 5시간 7분 13초만에 할 수 있다는 것을 알아냈다.		이동 횟수를 최소화할 수 있는 k값을 계산한 다음 18,433번만 옮기면 된다는 결론을 내렸다. 따라서 침이 세 개만 있을 때는 5천억년이 걸릴 일을 침 하나만 추가하면 5시간 7분 13초만에 할 수 있다는 것을 알아냈다.

Line 23:		Line 21:

	=== Sample Input ===		=== Sample Input ===
	~~{{\|~~ 1		1
	2		2
	28		28
	64 ~~\|}}~~		64
	=== Sample Output ===		=== Sample Output ===
	~~{{\|~~ 1		1
	3		3
	769		769
	18433 ~~\|}}~~		18433
	=== 풀이 ===		=== 풀이 ===
	{\| class="wikitable"		{\| class="wikitable" style="width:100%;"
	\|-		\|-
	\| 작성자		\| 작성자
Line 58:		Line 56:
	----		----
	[[문제분류]] [[경시대회준비반]]		[[문제분류]] [[경시대회준비반]]

imported>Unknown at 05:28, 7 February 2021

2021-02-07T05:28:13Z

New page

[http://online-judge.uva.es/p/v102/10254.html 원문보기]
----
인기도:C(A,B,C), 성공률:높음(낮음,보통,높음), 레벨:2(1~4)

=== About [[ThePriestMathematician]] ===
"하노이의 탑(Tower of Hanoi)" 퍼즐에 관한 고대 신화는 이미 잘 알려져 있다. 최근 밝혀진 전설에 의하면, 브라흐마나 수도사들이 64개의 원반을 한 쪽 침에서 다른 쪽 침으로 옮기는 데 얼마나 오래 걸리는지를 알아내고 나서는 더 빠르게 옮기는 방법을 찾아내자는 결론을 내렸다. 다음 그림은 침이 네 개인 하노이의 탑이다.
[http://online-judge.uva.es/p/v102/p10254b.jpg]
사원에 있는 수도사 중 한 명이 동료 수도사에게 침을 하나만 추가하면 1초에 원반을 하나씩 옮긴다고 할 때 한 나절이면 모든 원반을 옮길 수 있을 것이라고 알려주었다. 그가 제안한 방법은 다음과 같다.
{{|
# 맨 위에 있는 원반(맨 위에 있는 k개의 원반)을 다른 침으로 옮긴다.
# 침이 세 개 있는 경우에 쓰는 방법을 그대로 적용해서 나머지 n-k개의 원반(전체 원반의 개수를 n개라고 가정)을 목표 지점으로 옮긴다.
# 마지막으로 네 개의 침을 이용해서 맨 위에 있던 k개의 원반을 최종 목적지로 옮긴다.
|}}
이동 횟수를 최소화할 수 있는 k값을 계산한 다음 18,433번만 옮기면 된다는 결론을 내렸다. 따라서 침이 세 개만 있을 때는 5천억년이 걸릴 일을 침 하나만 추가하면 5시간 7분 13초만에 할 수 있다는 것을 알아냈다.

그 영리한 수도사가 제안한 네 개의 침을 사용하는 방법으로 원반을 옮기는 횟수를 계산하자. 원반은 한 번에 하나씩만 옮길 수 있으며 큰 원반을 작은 원반 위에 놓을 수는 없다. 이동 횟수를 구하려면 먼저 원반 이동 횟수를 최소화시킬 수 있는 k값을 구해야 한다.

=== Input ===
입력 파일은 여러 줄로 구성된다. 각 줄에는 0 이상 10,000 이하의 정수 N이 들어있으며, 이 값은 옮겨야 할 원반의 개수를 나타낸다. 파일 끝 문자가 들어오면 입력이 종료된다.

=== Output ===
입력된 각 줄에 대해 N개의 원반을 최종 위치로 옮기는 데 필요한 이동 횟수를 출력한다.

=== Sample Input ===
{{| 1
2
28
64 |}}
=== Sample Output ===
{{| 1
3
769
18433 |}}
=== 풀이 ===
{| class="wikitable"
|-
| 작성자
| 사용언어
| 개발시간
| 코드
|-
| 김상섭
| C++
| .
| [[ThePriestMathematician/김상섭]]
|-
| 문보창
| C++
| 1차(실패), 2차(5시간)
| [[ThePriestMathematician/문보창]]
|-
| 하기웅
| C++
| 2시간 30분
| [[ThePriestMathematician/하기웅]]
|}
=== 쓰레드 ===
----
[[문제분류]] [[경시대회준비반]]

ThePriestMathematician - Revision history

Maintenance script: Table transclusion repair v1

imported>Unknown at 05:28, 7 February 2021