N-Queens의 매운 맛 문제가 있길래 시도해봤는데 시간초과로 박살이 났다. 인풋으로 99999가 들어가는데 시간 초과가 나는건 자명했는데 아무 생각없이 정답률을 까먹었다. 대체 어떻게 푸는건가 싶어서 구글링해봤는데, 이 문제에만 특별히 적용되는 알고리즘이 있었다. 태그에 백트래킹이 붙어있지 않을 때 알아봤었어야 했는데...
8*8 체스보드에 8개의 퀸을 서로 공격하지 못하게 놓는 문제는 잘 알려져 있는 문제이다. 퀸은 같은 행, 열, 또는 대각선 위에 있는 말을 공격할 수 있다. 이 문제의 한가지 정답은 아래 그림과 같다.
이 문제의 조금 더 일반화된 문제는 Franz Nauck이 1850년에 제기했다.
N*N 보드에 N개의 퀸을 서로 다른 두 퀸이 공격하지 못하게 놓는 경우의 수는 몇 가지가 있을까?
이 문제는 N>3인 경우에 경우의 수가 적어도 1개 라는 것이 증명되어 있다. 예를 들어, N=26인 경우에 22317699616364044가지 방법이 있다.
N이 주어졌을 때, N*N 보드에 N개의 퀸을 서로 다른 두 퀸이 공격하지 못하게 놓는 한가지 경우를 출력하는 프로그램을 작성하시오.
입력
첫째 줄에 N이 주어진다. N은 8, 26, 213, 2012, 99991, 99999중 하나이다.
코드
최적화 할 여지가 굉장히 많지만 큰 의미가 없는 문제라 실행시간에 의미를 두지 않기로 했다.
import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args) throws Exception{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
int N = Integer.parseInt(br.readLine());
int[] sol = new int[N];
if(N % 6 != 2 && N % 6 != 3) {
// System.out.println("1");
int i = 0;
for(i = 0; i < N; i++) {
if(2*i+1 > N) break;
sol[i] = 2*i+1;
}
for(int k = i; k < N; k++) {
sol[k] = 2*(k-i+1);
}
}
else if(N % 6 == 2) {
// System.out.println("2");
for(int i = 0; i < N/2; i++) {
sol[i] = (i+1)*2;
}
sol[N/2] = 3;
sol[N/2+1] = 1;
int i = 0;
for(i = N/2+2; i < N-1; i++) {
sol[i] = 2*(i-N/2+1)+1;
}
// sol[N-1] = sol[N-2];
sol[N-1] = 5;
}else {
for(int i = 0; i < N/2-1; i++) {
sol[i] = (i+2)*2;
}
sol[N/2-1] = 2;
for(int i = N/2; i < N-2; i++) {
sol[i] = (i-N/2+2)*2+1;
}
sol[N-2]=1;
sol[N-1]=3;
}
StringBuilder sb = new StringBuilder();
for(int i = 0; i < N; i++) {
sb.append(sol[i]+"\n");
}
bw.write(sb.toString());
bw.flush();
// comb(0);
}
}
문제의 의의?
없다. 큰 도움이 되지 않는 문제다. 내가 풀이를 고안해내지 못해도 죄책감이 들지 않는 문제다. 도대체 이 알고리즘을 누가 앉은 자리에서 생각해낸단 말인가? 이 알고리즘을 모르는 개발자 100명을 가둬놓고 풀이를 시키면 누가 풀 수 있을까? 아이디어는 다이아몬드급 구현은 브론즈급 문제인데 왜 플래티넘5가 붙었는지 모르겠다. solved.ac 티어 한 끼 식사로 충분하다. 개인의 발전에는 도움이 되지 않으니 이 문제를 못 풀었다고 좌절하지 말자.
댓글