[BOJ C++] 16936 나3곱2

https://www.acmicpc.net/problem/16936

16936번: 나3곱2

 

문제 이해

순서가 섞여있는 크기 N의 수열이 주어지고, 기존의 수열을 찾는 문제였습니다.

수열은 이전 숫자에 2를 곱하거나 3을 나눴을 때의 수가 이전 숫자의 다음에 위치합니다.

 

 

입출력 조건

수열의 최대 크기는 100 이였으며 원소의 최대 크기는 10^18까지 가능하였기에 원소는 long long의 범위를 잡아야 한다 생각했습니다.

또 시간 제한은 2초였기에 100개의 원소가 있다고 생각했을 때 시간은 크게 제한적이지 않다 생각했습니다.

 

 

풀이

최대 크기가 100 이였기에 단순히 반복적인 방법을 생각했고 탐색과 재귀를 사용해서 최대 N^3의 방법이 가능하다고 판단했습니다.

또 곱하는 경우와 나누는 경우를 모두 확인하고 이전 상태로 돌아가기 위해 재귀로 구현하였습니다.

 

1. 입력 받은 수열을 오름차순으로 정렬합니다.

2. 가장 처음 수부터 배치하며 탐색을 시작합니다.

- 해당 숫자의 곱하기 2인 숫자가 있다면 해당 숫자를 다음 숫자로 넣어주고 해당 숫자를 사용했다는 표시를 해준 후 해당 숫자의 인덱스를 다시 재귀로 전달합니다.

- 해당 숫자의 곱하기 2인 숫자가 없다면 앞선 인덱스에서 나누기 3을 했을 때 같은 숫자가 있는지 확인하여 해당 숫자 사용여부를 확인하고 인덱스를 넘겨줍니다.

3. 위 2번 과정의 시작숫자를 바꿔주며 수행하고, 과정을 통해 N 크기의 수열이 완성되었을 때 반복문을 종료 하였습니다.

 

에러

visited 배열의 초기화를 위해 memset을 사용하였지만 헤더에 cstring을 선언해 주지 않아 런타임 에러가 발생하였습니다.

 

 

 

전체코드

https://github.com/JuneYoungDo/Algorithm/blob/master/16936_%EB%82%983%EA%B3%B12.cpp

GitHub - JuneYoungDo/Algorithm: This is a repository for additional problem solving in Baekjun.