dragon curve > 문제은행



문제은행

1167 : dragon curve

제한시간: 1000 ms    메모리제한: 64 MB
해결횟수: 2 회    시도횟수: 3 회   



r(S)란 함수를 0과 1로 이루어진 문자열 S를 뒤집은, 다음 보수를 취하는 함수라고 정의하자. 여기서 보수란 문자열 S의 문자 1과 0을 서로 바꿔주는 것을 뜻한다. 1001이라는 문자열의 보수는 0110이 된다.

다시 말해서 함수 r(S)란, 문자열 s를 뒤집고, 뒤집힌 문자열 안의 문자 1은 0으로, 문자 0은 1로 바꿔주는 함수이다. 그리고 다음과 같이 함수 함수 Sn을 정의하자.

S0 = 1 Sn = Sn-11r(Sn-1)
S0 부터 순서대로 몇 개의 생성되는 문자열을 보면 다음과 같다.

S0 = 1
S1 = 110
S2 = 1101100
S3 = 11011010b0100...

위를 통해서 생성된 S10의 문자열에 대응하여 움직이는 로봇을 만들어 보자. 이 로봇은 처음에 좌표계 (0, 0)에서 시작하여 매번마다 길이 1만큼 x y 좌표축에 대해 수직 혹은 수평의 움직임을 보이며 1초의 시간이 걸린다. k번째 움직일 때 S10의 k번째 문자가 1일 경우 현재 움직이는 방향에서 왼쪽방향으로 90도 회전을 하고 0일 경우는 오른쪽 방향으로 90도 회전을 한다. 처음에 움직일 경우는 로봇은 동쪽 방향을 향하고 있다. 아래는 규칙에 따라 움직 였을 때의 로봇의 움직임을 표시한 그림이다. 로봇은 하얀점 (0, 0)에서 시작하고 검은점이 위치한 (-32, 32)에서 움직임을 종료한다.

e3050b66a1b29a01767400d7560a4131_1449741
 

S10에 대해 프로그램을 구현 할 때 는 간단한 반복문을 통해서 문제가 해결이 가능하다. 하지만 S30에 대해서라면 그리 간단하지는 않다. 로봇이 위에서처럼 (0, 0)에서 동쪽 방향을 바라보며 작동을 시작하고 231초에 동작을 정지 한다고 하였을 때 임의의 시간에 어떤 좌표에 위치 해 있는지 알아내는 프로그램을 작성하라.




입력은 여러개의 테스트 케이스로 이루어져 있으며 각각의 테스트 케이스는 0이상의 정수 n(n≤109)이 입력 된다.
테스트 케이스의 개수는 5,000개 이하이며 입력은 -1을 입력으로 받으면 종료한다.
전체 입력 데이터 중 40%는 n≤2,047 이하의 입력이 주어진다.




테스트 케이스 n에 대해서 S30을 이용해 그림을 그렸을 때, n초 이후에 위치를 다음과 같이 한줄에 출력한다. (x, y) 여기서 x, y 는 각각 x좌표의 값 y좌표의 값을 뜻한다.



1
2
3
2048
150000
-1
(1,0)
(1,1)
(0,1)
(-32,32)
(9648,-31504)






HancomEducation E-mail : hancomc@hotmail.com, comkiwer@naver.com Tel : 031-388-0999 FAX : 031-388-0996 정올소개 이용약관 개인정보처리방침
경기도 안양시 동안구 호계동 1065-10 협성골드프라자 601호, 경기도 안양시 동안구 평촌대로 109 협성골드프라자 601호
Copyright@2010-2015 jungol. All right reserved.