이동식 저장소

16936. 나3곱2 본문

Problem Solving/BOJ

16936. 나3곱2

해스끼 2022. 7. 2. 10:42
 

16936번: 나3곱2

나3곱2 게임은 정수 하나를 이용한다. 가장 먼저, 정수 x로 시작하고, 연산을 N-1번 적용한다. 적용할 수 있는 연산은 두 가지 있고, 아래와 같다. 나3: x를 3으로 나눈다. x는 3으로 나누어 떨어져야

www.acmicpc.net


정수 x에 다음 두 연산 중 하나를 N1번 적용하여 길이가 N인 수열 A를 만든다.

  • x3으로 나눈다. 이때 x는 3으로 나누어떨어져야 한다.
  • x2를 곱한다.

A의 수를 무작위로 섞은 수열 B가 주어졌을 때, A를 구하는 문제이다.


A에 속하는 정수 y에 대해, y 앞에는 3y 또는 y/2가 올 수 있고, y 뒤에는 y/3 또는 2y가 올 수 있다. 우리는 이 수열의 올바른 순서를 찾아야 한다. 위상 정렬처럼 생각해도 좋다.

 

연산을 잘 보면, 곱하는 수와 나누는 수가 23으로 서로 다르다. 그렇다면 연산을 계속 적용했을 때 나왔던 수가 또 나오는 경우는 불가능하다. 따라서 A가 존재한다고 하더라도 서로 다른 A가 여러 개 존재할 수는 없다.

 

이로써 스페셜 저지 태그와 출력 문단의 `가능한 정답이 여러가지인 경우에는 아무거나 출력한다`는 낚시임을 알 수 있다. 이런.. ㅋㅋ

 

출력 문단에서 항상 정답이 존재하는 경우만 입력으로 주어진다고 했으니, 이제 수열을 만들기만 하면 된다.


 

수열 A가 유일하므로 A의 시작 원소 x도 유일하다. sB에 대해 3sB이고 s/2Bs를 찾아서, s를 시작 원소로 하여 A를 만들면 된다.

 

N이 최대 100이지만, 정답이 유일하므로 재귀 탐색으로 정답을 찾아도 시간 초과가 발생하지 않는다.


'Problem Solving > BOJ' 카테고리의 다른 글

1014. 컨닝  (0) 2022.07.19
22343. 괄호의 값 비교  (0) 2022.07.04
13325. 이진 트리  (0) 2022.06.19
2637. 장난감 조립  (2) 2021.09.28
22996. 유니온 파인드 복원  (0) 2021.08.26