하노이 탑


이전까지 풀었던 고전 하노이 탑을 생각하고 문제에 접근한다면 큰 코 다칠 수 있다.

이번 문제는 기존 문제와 결이 조금 다르며 3개의 원판을 다른 곳으로 이동시킬 때 2^n-1번의 이동이 일어난다는 사실을 고지해준다.

고지된 바를 이용하고 모듈러 연산을 잘 알고있어야 문제를 풀 수 있다.


풀이 방식


  1. 가장 큰 원판으로 모든 원판을 옮겨야 한다.

  2. 가장 큰 원판의 크기(n) 부터 시작해 하나씩 작은 크기의 원판으로 재귀 함수를 호출한다.

  3. 원판이 이동시키려는 위치에 이미 위치한다면 다음 재귀를 호출한다.

  4. 원판이 이동시키려는 위치에 없다면 현재 위치와 이동위치기 아닌 임의 위치로 이동시키는 재귀를 호출한다.

  5. 위 4번의 경우 가장 큰 원판 위에 자신 보다 큰 크기의 원판이 이미 순서대로 쌓여있고 그 위에 자기 자신을 옮기고(+1) 나머지 원판들을 자신 위에 옮긴다(+ 2^size -1). 즉, 2^size 만큼 횟수가 추가된다.

  6. 모듈려 연산을 통해 100000회가 안넘어가지도록 나눠준다.


// 2022-03-15
// 2022-03-21
// https://www.acmicpc.net/problem/2270

import java.io.*
import java.util.*
import kotlin.math.pow

lateinit var pos:IntArray
lateinit var modArr:IntArray
const val mod = 1000000
var answer = 0

fun main()= with(BufferedReader(InputStreamReader(System.`in`))) {
    val n =readLine().toInt()
    modArr = IntArray(100001)
    modArr[1]=1

    // 모듈러 연산을 통해 미리 계산
    for(i in 2..100000){
        modArr[i] = (modArr[i-1]*2) %1000000
    }

    pos = IntArray(n+1)
    val (a,b,c) = readLine().split(' ').map{it.toInt()}
    readLine().split(' ').map{it.toInt()}.forEach { pos[it]=1 }
    readLine().split(' ').map{it.toInt()}.forEach { pos[it]=2 }
    readLine().split(' ').map{it.toInt()}.forEach { pos[it]=3 }

    re(n,pos[n])    // 가장 큰 원판부터 재귀 호출 시작
    println(pos[n]) // 옮겨야 하는 곳(가장 큰 원판의 현재 위치)
    println(answer) // 옮겨진 횟수 mod 1000000
}

fun re(size:Int, to:Int){
    if(size==0) return  // 원판 크기가 0이면 반환

    // 원판이 원하는 위치에 있으면 그대로 다음 재귀 호출
    if(pos[size]==to) re(size-1,to) 
    else{

        // 중간 위치 찾기
        var tmp=0
        for(i in 1..3) if(i!=to && pos[size]!=i) tmp=i
        
        // 다음 재귀부터는 중간위치를 원하는 위치로 호출
        re(size-1,tmp)

        // 횟수 추가
        answer = (answer + modArr[size])%1000000
    }
}