백준 문제 11729

세 개의 장대가 있고 첫 번째 장대에는 반경이 서로 다른 n개의 원판이 쌓여 있다. 각 원판은 반경이 큰 순서대로 쌓여있다. 이제 수도승들이 다음 규칙에 따라 첫 번째 장대에서 세 번째 장대로  옮기려 한다.

1. 한 번에 한 개의 원판만을 다른 탑으로 옮길 수 있다.
2. 쌓아 놓은 원판은 항상 위의 것이 아래의 것보다 작아야 한다.(중간 과정 역시 그래야함)

이 작업을 수행하는데 필요한 이동순서를 출력하는 프로그램을 작성하라

import java.util.Scanner;

public class Main {
	int[][] process=new int[1050000][2];
	int count=0;
	
	public void move(int height, int start, int end) {
		int mid=6-start-end;
		if(height==1) {
			process[count][0]=start;
			process[count][1]=end;
			count++;
		}
		else {
			move(height-1,start,mid);
			process[count][0]=start;
			process[count][1]=end;
			count++;
			move(height-1,mid,end);
		}
	
	}
	public static void main(String[] args) { 
		Scanner sc=new Scanner(System.in);
		Main main=new Main();
		int height=sc.nextInt();
		
		main.move(height, 1, 3);
		System.out.printf("%d%n",main.count);
		for(int i=0;i<main.count;i++)
			System.out.printf("%d %d%n", main.process[i][0],main.process[i][1]);
	}
}

자바로 짠 코드는 사실 시간제한에 걸려 성공하지 못했다. C로 짜면 훨씬 나을 것 같아서 C로 짰더니 시간제한 안에서 성공 자바에서는 아직 더 빠르게 하는 방법을 찾지 못했다.

다른 것 보다 출력하는 데 시간이 굉장히 오래 걸리는 게 문제인데, println을 쓰는 게 아니라 outputstream을 써서 다시 한번 짜 봐야겠다. 거의 같을 것 같기는 하지만.

아래는 C로 짠 코드. 문법만 고친 것이고 완전히 같은 코드이다.

#include<stdio.h>

int process[1050000][2];
int count=0,N;
	
void move(int height, int start, int end) {
	int mid=6-start-end;
	if(height==1) {
		process[count][0]=start;
		process[count][1]=end;
		count++;
	}
	else {
		move(height-1,start,mid);
		process[count][0]=start;
		process[count][1]=end;
		count++;
		move(height-1,mid,end);
    }
}
int main() { 
	scanf("%d",&N);
       
	move(N, 1, 3);
	printf("%d \n",count);
	for(int i=0;i<count;i++)
		printf("%d %d \n",process[i][0],process[i][1]);
    return 0;
}