[Python] 10407번 2 타워

728x90

10407번: 2 타워

2 타워의 높이 H는\[2^{2^{2^{\cdot^{\cdot^{\cdot 2}}}}}\]에서 숫자 2가 나타나는 횟수로 정의된다. 2 타워의 값은 해당 표현식의 값으로 정의된다. 예를 들어, 높이 1의 2 타워 값은 2이고, 높이 2의 2 타워

www.acmicpc.net

24/01/20

수학 문제로, 찍어서 맞출 수도 있으나 여기서는 증명을 소개하도록 하겠다.

문제 접근 방식:

결론만 이야기 하자면, $H = 1$일 때는 나머지가 $2$이고, 그 외에는 $1$이다.

일단 $H=1$일 때는 2타워의 값은 $2$이므로, $3$으로 나눈 나머지가 $2$이다.

$2$를 짝수 번 곱하면 그 숫자를 $3$으로 나눈 나머지는 $1$이다.

그 이유는 나머지 연산의 성질에 의하여, $2 \times 2 \times \cdots \times 2 \equiv 4 \times \cdots \times 4 \equiv 1 \times \cdots \times 1 \equiv 1$이기 때문이다.

근데 $H > 1$일때는 $2$를 짝수 번 곱하는 것이므로, 그 숫자가 뭐든 간에 $3$으로 나눈 나머지가 $1$임을 알 수 있다.

따라서, 이를 그대로 구현하면 된다.

아래는 내가 위의 접근 방식과 같이 작성한 파이썬 코드이다. 더 보기를 누르면 확인할 수 있다.

H = int(input())
if H == 1:
    print(2)
else:
    print(1)

기록(記錄)