백준 16936번: 나3곱2

문제

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

16936번: 나3곱2

---

풀이

정수 x가 있을 때 다음과 같은 2개의 연산을 N-1번 적용하는 게임을 이용하여 만든 수열 a를 섞은 수열 b를 입력받고 a를 구하는 문제입니다.

• 나3: x를 3으로 나눈다. x는 3으로 나누어 떨어져야 한다.
• 곱2: x에 2를 곱한다.

---

코드

C언어

먼저 수열 b를 qsort를 이용하여 오름차순으로 정렬합니다. 방문 여부를 확인해주는 bool형 정수 배열 visited를 선언해주고 i를 포함한 for문 안에서 dfs 함수를 실행하면서 수열 a에 첫 번째로 들어갈 값(b[i])을 정합니다.

dfs 함수 안에서 b[idx]의 방문 여부를 확인한 뒤에 방문한 적이 없다면 방문했다고 표시한 뒤에 a[dpth]에 b[idx]값을 넣어줍니다. 이후에 a[dpth]가 3으로 나누어 떨어진다면 나3 연산을 실행할 수 있습니다. 이때 나3 연산을 실행한다면 a[dpth + 1]은 a[dpth]보다 작기 때문에 i를 포함한 for문을 이용하여 b[idx - 1]부터 b[0]까지 확인합니다. b[i] = a[dpth] / 3이라면 dfs를 재귀적으로 실행합니다.

아래의 i를 포함한 for문에서는 b[idx + 1]부터 b[n - 1]까지 확인하는데 그 이유는 곱2 연산을 실행하게 되면 a[dpth + 1]은 a[dpth]보다 크기 때문입니다. b[i] = a[dpth] * 2라면 위와 마찬가지로 dfs를 재귀적으로 실행합니다.

dfs함수가 끝나지 않았을 때 위의 두 for문이 모두 종료된다면 어떤 연산을 사용해도 a[dpth + 1]를 채울 수 없다는 뜻이기 때문에 이전(dpth - 1)으로 돌아가게 되며 그전에 b[idx]를 다른 곳에 사용할 수도 있기 때문에 visited[idx]를 0으로 초기화합니다.

dpth가 n - 1이 되면 수열 a를 완성한 것이기 때문에 i를 이용한 for문을 이용하여 수열 a를 순서대로 출력한 후 exit(0)을 이용하여 프로그램을 종료합니다.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
long long int *a, *b;
int n, *visited;
int compare(const void* a, const void* b) {
	long long int o1 = *(long long int*)a;
	long long int o2 = *(long long int*)b;
	if (o1 > o2) return 1;
	else if (o1 < o2) return -1;
	else return 0;
}
void dfs(int idx, int dpth) {
	if (!visited[idx]) {
		visited[idx] = 1;
		a[dpth] = b[idx];
		if (dpth == n - 1) {
			for (int i = 0; i < n; i++) {
				printf("%lld ", a[i]);
			}
			exit(0);
		}
		if (a[dpth] % 3 == 0) {
			for (int i = idx - 1; i >= 0; i--) {
				if (b[i] == a[dpth] / 3) {
					dfs(i, dpth + 1);
				}
			}
		}
		for (int i = idx + 1; i < n; i++) {
			if (b[i] == a[dpth] * 2) {
				dfs(i, dpth + 1);
			}
		}
		visited[idx] = 0;
	}
}
main() {
	scanf("%d", &n);
	a = (long long int*)malloc(sizeof(long long int) * n);
	b = (long long int*)malloc(sizeof(long long int) * n);
	for (int i = 0; i < n; i++) {
		scanf("%lld", &b[i]);
	}
	qsort(b, n, sizeof(long long int), compare);
	visited = (int*)malloc(sizeof(int) * n);
	for (int i = 0; i < n; i++) {
		dfs(i, 0);
	}
}

자바

위의 C언어를 이용한 풀이와 동일한 방법으로 다른 점이라면 Stringbuilder를 이용하여 한꺼번에 출력한다는 것입니다.

import java.io.IOException;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {

    static int n;
    static long[] a, b;
    static boolean[] visited;

    public static void dfs(int idx, int dpth) {
        if (!visited[idx]) {
            visited[idx] = true;
            a[dpth] = b[idx];
            if (dpth == n - 1) {
                StringBuilder sb = new StringBuilder();
                for (int i = 0; i < n; i++) {
                    sb.append(a[i]).append(" ");
                }
                System.out.println(sb);
                System.exit(0);
            }
            if (a[dpth] % 3 == 0) {
                for (int i = idx - 1; i >= 0; i--) {
                    if (b[i] == a[dpth] / 3) {
                        dfs(i, dpth + 1);
                    }
                }
            }
            for (int i = idx + 1; i < n; i++) {
                if (b[i] == a[dpth] * 2) {
                    dfs(i, dpth + 1);
                }
            }
            visited[idx] = false;
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        a = new long[n];
        b = new long[n];
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        for (int i = 0; i < n; i++) {
            b[i] = Long.parseLong(st.nextToken());
        }
        Arrays.sort(b);
        visited = new boolean[n];
        for (int i = 0; i < n; i++) {
            dfs(i, 0);
        }
    }
}

 

---

결론

처음에 문제를 꼼꼼하게 읽지 않아서 배열 b의 원소가 최대 10^18이 될 수 있다는 조건이 있었으나 long형이 아닌 int형을 써서 틀렸었습니다. 또한 처음에 이 문제를 풀 때 main 함수 안에서 dfs 함수를 실행하기 전에 Arrays.fill(visited, false) 등을 사용해서 visited 배열을 초기화했었는데 이 문제의 풀이를 작성하면서 코드를 다시 읽어보니 그럴 필요가 없다는 것을 알게 되었습니다.

문제를 꼼꼼히 읽는 습관, 어떤 과정의 필요 여부 등을 꼼꼼하게 살펴야겠습니다.