문제 AF: [2023 충북정올 예선(초등부) 3번] 개미는 어디 있을까?
[만든사람 : ]
제출문제리스트
문제 설명
단테는 개미집에 관한 다큐멘터리를 보다가 개미가 개미집에서 어느 곳에 있는지 궁금해졌다. 개미집과 유사한 이진 트리 구조를 활용하기로 하였다. 개미집은 수 많은 방들로 구성되어 있으며 동그라미로 방을 나타내기로 했다. 개미집은 깊이가 증가할수록 방이 많아지는 구조인데, 한 방에서는 바로 아래로 최대 2개의 방을 만들 수 있다.
아래 그림은 깊이가 3인 개미집이고 왼쪽 개미집은 깊이가 3인 개미집들 중에서 최대 방 개수를 갖는 개미집이다. 오른쪽에는 깊이가 3인 다른 개미집이다.
방의 번호는 1번부터 시작하고 최대로 뻗어져 있는 개미집 모양을 기준으로 방 번호가 정해진다. 즉, 방 번호는 1씩 증가하지 않을 수 있다.
개미집의 상태를 나타내기 위해 최대로 뻗어져있는 개미집의 모양을 기준으로 방이 있으면 1, 없으면 0으로 표현한다. 예를 들어, 깊이가 3인 개미집은 총 7개의 방 상태로 표현할 수 있는데, 왼쪽 개미집의 경우 1 1 1 1 1 1 1 로 표현할 수 있고, 오른쪽 개미집의 경우 1 1 1 0 1 0 1 으로 표현할 수 있다.(4, 6번 방은 없다.)
개미는 개미집의 최상단 방부터 시작하여 왼쪽 또는 오른쪽으로 이동할 수 있다.(왼쪽 = 0, 오른쪽 = 1) 예를 들어 1 0이 입력되면 오른쪽 방으로 이동한 뒤 왼쪽 방으로 이동을 한다. 개미가 가야하는 방향에 한 번이라도 방이 없다면 개미는 이동하지 않으며 마지막에 있던 방에 가만히 있으며 그 이후 입력된 이동은 모두 무시한다.
개미집의 상태와 개미의 이동방향 정보를 입력받아 개미의 최종 위치를 출력하는 프로그램을 작성하시오.
아래 그림은 깊이가 3인 개미집이고 왼쪽 개미집은 깊이가 3인 개미집들 중에서 최대 방 개수를 갖는 개미집이다. 오른쪽에는 깊이가 3인 다른 개미집이다.
방의 번호는 1번부터 시작하고 최대로 뻗어져 있는 개미집 모양을 기준으로 방 번호가 정해진다. 즉, 방 번호는 1씩 증가하지 않을 수 있다.
개미집의 상태를 나타내기 위해 최대로 뻗어져있는 개미집의 모양을 기준으로 방이 있으면 1, 없으면 0으로 표현한다. 예를 들어, 깊이가 3인 개미집은 총 7개의 방 상태로 표현할 수 있는데, 왼쪽 개미집의 경우 1 1 1 1 1 1 1 로 표현할 수 있고, 오른쪽 개미집의 경우 1 1 1 0 1 0 1 으로 표현할 수 있다.(4, 6번 방은 없다.)
개미는 개미집의 최상단 방부터 시작하여 왼쪽 또는 오른쪽으로 이동할 수 있다.(왼쪽 = 0, 오른쪽 = 1) 예를 들어 1 0이 입력되면 오른쪽 방으로 이동한 뒤 왼쪽 방으로 이동을 한다. 개미가 가야하는 방향에 한 번이라도 방이 없다면 개미는 이동하지 않으며 마지막에 있던 방에 가만히 있으며 그 이후 입력된 이동은 모두 무시한다.
개미집의 상태와 개미의 이동방향 정보를 입력받아 개미의 최종 위치를 출력하는 프로그램을 작성하시오.
입력 설명
첫 번째 줄에 개미집의 깊이(d)가 자연수로 입력된다.(1≤d≤6)
두 번째 줄에 개미집의 각 방의 상태가 공백으로 분리되어 입력된다.(0 : 없음, 1 : 있음)
세 번째 줄에 개미의 이동 방향이 공백으로 분리되어 입력된다.(0 : 왼쪽, 1 : 오른쪽)
두 번째 줄에 개미집의 각 방의 상태가 공백으로 분리되어 입력된다.(0 : 없음, 1 : 있음)
세 번째 줄에 개미의 이동 방향이 공백으로 분리되어 입력된다.(0 : 왼쪽, 1 : 오른쪽)
출력 설명
개미가 마지막에 위치하고 있는 방의 번호를 출력한다.
입력 예시 Copy
3
1 1 1 1 1 1 1
0 1
출력 예시 Copy
5