[백준] 34099번. 뭔가 이미 있을 것 같은 순열 문제(JAVA)

문제

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

---

풀이(15분)

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));
        StringTokenizer st;

        int T = Integer.parseInt(br.readLine());
        StringBuilder sb = new StringBuilder();
        while(T-- > 0){
            st = new StringTokenizer(br.readLine());
            int N = Integer.parseInt(st.nextToken());
            int K = Integer.parseInt(st.nextToken());

            if(K != 1){ // 차이가 1이 아니라면
                for(int i = 1; i <= N; i++){ // 그냥 오름차순으로 끝내도 됨
                    sb.append(i).append(" ");
                }
            }else{ // 아니라면
                if(N < 4){ // 길이가 3짜리는 불가능함
                    sb.append(-1);
                }else{
                    // 짝수부터 시작해서 올리고
                    for(int i = 2; i <= N; i += 2){
                        sb.append(i).append(" ");
                    }
                    // 홀수도 연속하게
                    for(int i = 1; i <= N; i +=2){
                        sb.append(i).append(" ");
                    }
                }
            }
            sb.append("\n");
        }
        System.out.println(sb);
    }
}

---

문제 풀이 전략

 

문제를 천천히 이해하는 것이 얼마나 중요한지 다시금 깨달은 문제이다.

인접한 두 수의 차이가 K가 아닌 수열을 구하라. 정답은 아무거나 상관없다.

-> 이 말을 보고 생각한 것이 하나 있다.

-> 오름차순으로 1~N을 나열한다면, 그냥 차이가 1이 아닌 건 전부 다 되는 거잖아?

 

 그렇기에 K!= 1인 것은 모두 오름차순으로 끝내버렸다.

 

만약 K가 1이라면?

길이가 3일 때까지는 안 된다.

길이가 4일 때부터는 2 4 1 3 같이 짝수를 연달아서 나열하고, 홀수를 연달아서 나열하면 된다.

 

즉, 문제를 잘 분석하고 예시를 찾아가다 보면 생각보다 간단하게 해결되는 문제인 것이다!