백준) 16936번: 나3곱2 in C

Problem.

16936번: 나3곱2

Solution.

이 문제에는 두 가지 놓치거나 간과하기 쉬운 포인트들이 있다.

1) 수열 B에 포함된 각 숫자는 10^18 보다 같거나 작은 자연수이다. 즉 int 형이 아니라 long long 형(64bit)을 써야 한다는 것.

2) "가능한 정답이 여러가지인 경우에는 아무거나 출력한다." 라고 써져 있지만 사실은 정답은 하나밖에 없다. 나3곱2 연산으로 만들어지는 수열에는 순환이 생기지 않기 때문. (예. 2->4->8->2->4... 이런 경우는 없다.)

 

처음엔 DFS를 이용해서 풀려고 했다.

N개의 숫자를 하나씩 체크해가며 현재 값에다 2를 곱하거나 3을 나눈 값이 수열에 있다면 또 그 값을 가지고 동일한 과정으로 나머지 수열 속 숫자들에 대해서 체크를 해나가며 결과값을 출력해보기로 했다.

DFS로 만든 코드는 다음과 같았다. 

#include <stdio.h>

int arr[100], checked[100];
int N, k = 1;

void dfs(int depth, int curr){
	int i;
	
	if(depth == N-1){
		int k, j, temp = 0;
		for(j=0;j<N;j++)
			for(k=0;k<N;k++){
				if(checked[k] == temp){
					printf("%d ", arr[k]);
					temp++;
				}
			}
		printf("\n");
		return;
	}
	
	i = 0;
	
	while(i<N){
		if(checked[i] == -1){
			if((arr[curr] / 3 == arr[i]) && (arr[curr] % 3 == 0)){
				checked[i] = depth + 1;
				dfs(depth + 1, i);
			}else if(arr[curr] * 2 == arr[i]){
				checked[i] = depth + 1;
				dfs(depth + 1, i);
			}
		}
		i++;
	}
	checked[curr] = -1;
};

int main(){
	int i;
	
	scanf("%d", &N);
	
	for(i=0;i<N;i++){
		scanf("%d", &arr[i]);
		checked[i] = -1;
	}
	
	for(i=0;i<N;i++){
		checked[i] = 0;
		dfs(0, i);
		checked[i] = -1;
	}
	
	return 0;
}

문제에 나온 Testcase에 대해서는 답이 잘 나왔지만 제출했을 때는 런타임 초과가 떴다. (long long이 아니라 int 형을 써서 어차피 오답이었다.)

시간복잡도가 더 낮은 방법이 필요했다.

 

간선과 그래프를 이용해보기로 했다.

예를 들어,

4, 8, 6, 3, 12, 9 가 주어졌을 때,

먼저 4에 대해서 나머지 숫자들과 비교해서 '나3', '곱2' 연산 시 나오는 값이면 (여기서는 8, 곱2)

4->8

이렇게 방향성이 있는 간선으로 이어주기로 한다.

나머지 수열 속 숫자들에 대해서 이러한 과정을 반복하면

4->8, 6->12, 3->6, 12->4, 9->3 다섯 개의 간선이 나오고 이를 이어주면

9->3->6->12->4->8이라는 이 문제의 답이 나온다.

 

C언어에서 그래프를 나타내기 위해 graph 2차원 배열과 checked 1차원 배열을 사용했다.

9->3->6->12->4->8 그래프를 2차원 배열로 표현하면 다음과 같다.

	4	8	6	3	12	9
4	0	1	0	0	0	0
8	0	0	0	0	0	0
6	0	0	0	0	1	0
3	0	0	1	0	0	0
12	1	0	0	0	0	0
9	0	0	0	1	0	0

즉 행의 값->열의 값 간선이 존재하면 1로 표시를 했다.

이렇게 배열로 표시하면 각 행과 열에서는 모두 0인 곳이 존재한다.

위 예시에서는 행에는 8, 열에는 9인데 이는 각각 끝점과 시작점을 의미한다.(9->...->8)

checked 배열을 이용해 시작점을 구했다.

 

최종 코드는 다음과 같다.

Code.

#include <stdio.h>

int checked[100] = {0, };

int graph[100][100] = {0, };
long long arr[100];
int N;

void print(int curr){
	int i;
	
	for(i=0;i<N;i++){
		if(graph[curr][i]){
			printf("%lld ", arr[i]);
			print(i);
			break;
		}
	}
	
	return;
}

int main(){
	int i, j, start;

	scanf("%d", &N);
	
	for(i=0;i<N;i++){
		scanf("%lld", &arr[i]);
	}

	for(i=0;i<N;i++){
		for(j=0;j<N;j++){
			if(arr[i] * 2 == arr[j] || ((arr[i] / 3 == arr[j]) && (arr[i] % 3 == 0))){
				graph[i][j] = 1;
				checked[j] = 1;
			}
		}
	}
	
	for(i=0;i<N;i++){
		if(!checked[i]){
			start = i;
			break;
		}
	}
	
	printf("%lld ", arr[start]);
	print(start);
	
	return 0;
}

 

이 문제를 푸니까 낙곱새가 먹고 싶어졌다.