[백준, Java] 13018번, 특이한 수열(애드 훅)

문제 링크

13018번: 특이한 수열

---

주의사항

• JAVA를 사용하여 프로그램을 사용하였습니다.
• 백준에서 코드를 작성하였을 때 아래 형태에서 Main에서 결과가 출력되어야 합니다.

public class Main{ 	
	public static void main(String[] args){
    }
}

---

문제 설명

---

접근 방법

이 문제에 핵심

1. 수열의 길이는 n이며, 1 ~ n까지의 수는 각 한번만 등장합니다.

2. i와 A[i]의 GCD(최대 공약수) > 1이 만족하는 개수가 정확히 k개를 만족해야합니다. 

3. 만족하는 수열을 결과로 출력합니다.

 

알고리즘 진행 순서.

 

1. 입력된 정보를 저장합니다.

 

2. 인접한 수 교환을 통한 규칙을 이용해서 조건에 만족하는 k개가 되도록 탐색합니다.

 

3. 탐색이 끝난 뒤 구한 수열을 결과로 출력합니다.

 

 

인접한 수 교환

 

1 ~ n까지 수열을 순차적으로 표현하면

 

1	2	...	n-1	n
1	2	...	n-1	n

 

(1, 1)을 제외한 모든 수열의 값은 조건에 만족합니다.

→ 항상 GCD(최대 공약수)가 자기 자신이기 때문입니다.

 

즉, n == k일 때는 불가능한 수열입니다.

→ n == k일 때는 Impossible을 결과로 출력합니다.

 

또다른 규칙으로는 인접한 수끼리는 항상 GCD(최대 공약수)의 값은 항상 1입니다.

 

 

GCD(2, 3) = 1

 

GCD(3, 4) = 1

 

GCD(4, 5) = 1

 

....

 

또한 GCD(1, ?)의 값은 항상 1입니다.

 

 

처음에 모든 수열의 값이 순차적으로 이루어졌다고 가정하면

 

K가 되도록 수열을 설정하려면

 

N - K - 1개를 인접한 수로 교환해야 합니다.

→ -1을 하는 이유는 (1, 1)이 있어서 1번은 벌써 만족하지 않기 때문입니다.

 

그러면 이제 N - K - 1개가 0이 되도록 인접한 수끼리 교환을 진행합니다.

 

 

교환을 진행할 때에는 2개의 수가 바뀌는 것임으로 2씩 감소해야 합니다.

 

N - K - 1개가 홀수이면???

→ 맨 끝의 수를 1과 교환함으로써 만족하게 합니다.

 

Why??

 

1을 사용했다는 것은 이미 제외했기 때문에, 1과 교환함으로써 1개가 더 제외되는 것이기 때문입니다.

 

 

예제입력 2.

1. 입력된 정보를 저장합니다.

 

N : 4

 

K : 2

 

1	2	3	4
1	2	3	4

 

2. 인접한 수 교환을 통한 규칙을 이용해서 조건에 만족하는 k개가 되도록 탐색합니다.

 

 

인접한 수를 교환해야 하는 개수 : N - K - 1 = 4 - 2 - 1 = 1개

 

인접한 수를 교환할 때에는 2개씩 바뀌기 때문에 인접한 수와 교환할 수 없습니다.

 

남은 수가 홀수로 남아있기 때문에

 

1과 4을 교환합니다.

 

 

1	2	3	4
4	2	3	1

 

GCD(1, 4) = 1(X)

 

GCD(2, 2) = 2(O)

 

GCD(3, 3) = 3(O)

 

GCD(4, 1) = 1(X)

 

 

3. 탐색이 끝난 뒤 구한 수열을 결과로 출력합니다.

 

{4, 2, 3, 1}을 결과로 출력합니다.

 

 

 

• BufferedReader를 사용하여 입력되는 정보를 저장합니다.
• StringTokenizer를 이용하여 N과 K를 띄어쓰기 기준 구분합니다.
• N == K일 때에는 Impossable을 BufferedWriter 저장합니다.
• 바꿔야 하는 개수 (N-K-1)을 구해서 인접한 수 교환을 진행합니다.
• 남은 개수가 1이면 1과 마지막 수를 교환합니다.
• 교환이 끝난 뒤 수열을 BufferedWriter 저장합니다.
• BufferedWriter에 저장된 결과를 출력합니다.

• swap함수는 두 수의 위치를 교환하는 함수입니다.

 

결과코드

import java.io.*;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException {
        //입력값 처리하는 BufferedReader
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        //결과값 출력하는 BufferedWriter
        BufferedWriter bw= new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine()," ");
        //입력값 저장
        int N = Integer.parseInt(st.nextToken());
        int K = Integer.parseInt(st.nextToken());
        int[] arr = new int[N];
        //n == k일 때는 만들 수 없는 수열
        if(N == K){
            bw.write("Impossible");
        }else{		//n != k일 때
            //순차적인 수열 초기화
            for(int i=0;i<N;i++){
                arr[i] = i + 1;
            }
            //교환해야 하는 개수, 점화식 : n - k - 1
            int dif = N- K - 1;
            //현재 인덱스
            int idx = 1;
            //교환 진행
            while(dif > 1){
                swap(arr, idx, idx+1);
                idx+=2;
                dif-=2;	//2개수의 수가 바뀌므로 2개씩 감소
            }
            //홀수일 때 1과 마지막 수 변경
            if(dif == 1){
                swap(arr, 0, N-1);
            }
            StringBuilder sb = new StringBuilder();
            //탐색한 수열 StringBuilder 저장
            for(int i=0;i<N;i++){
                sb.append(arr[i]).append(" ");
            }
            //결과 BufferedWriter 저장
            bw.write(sb.toString());
        }
        bw.flush();		//결과 출력
        bw.close();
        br.close();
    }
    //서로의 수를 교환하는 함수
    static void swap(int[] arr, int idx1, int idx2){
        int temp = arr[idx1];
        arr[idx1] = arr[idx2];
        arr[idx2] = temp;
    }
}