[Baekjoon 20921] 그렇고 그런 사이 - JAVA

[Silver I] 그렇고 그런 사이 - 20921

문제 링크

성능 요약

메모리: 14776 KB, 시간: 152 ms

분류

해 구성하기, 그리디 알고리즘

문제 설명

신수동 최고의 인싸 환주는 오늘도 인기가 많다. 그 인기는 정말 대단해서 대나무숲에서는 매일 환주의 이름이 쏟아진다.

환주에게는 그 인기의 비결이 있었는데, 바로 자신이 원하는 두 명을 그렇고 그런 사이로 만들 수 있는 것이다!

환주가 그렇고 그런 사이를 만드는 방법은 다음과 같다.

•  $1$번 사람부터 $N$번 사람까지 $N$명을 일렬로 세운다.
• 모든 사람에게 $1$부터 $N$까지 양의 정수 중 하나가 적힌 쪽지를 나눠준다. 쪽지에 적힌 정수는 중복되지 않는다.
• 서로 다른 두 사람을 골랐을 때, 왼쪽에 있는 사람이 오른쪽에 있는 사람보다 쪽지에 적힌 정수가 더 크다면, 이 두 사람은 그렇고 그런 사이가 된다.
• 놀랍게도 한 사람이 여러 사람과 그렇고 그런 사이일 수도 있다.

21세기의 큐피드 환주는 썸과 연애 상담이 너무 많이 와서 힘들다. 그래서 환주는 한 번에 여러 개의 그렇고 그런 사이를 만들려 한다. 하지만 너무 많이 만들면 미풍양속에 저해되고, 너무 적게 만들면 솔로들이 많아지기 때문에, 정확히 $K$개의 그렇고 그런 사이를 만들려 한다.

환주는 저 멀리서 달려오는 $N$명의 친구들을 보았다. 재빨리 $K$개의 그렇고 그런 사이를 만들어 주지 않으면, 저들은 환주의 안티팬이 될지도 모른다!

입력

정수 $N$, $K$가 주어진다. ($2 \leq N \leq 4,242$, $0 \leq K \leq \frac{N(N-1)}{2}$)

출력

 
$N$개의 정수 $v_1, v_2, \cdots, v_N$을 공백 단위로 출력한다.
 
$v_i$는 $i$번째 사람이 받은 쪽지에 적힌 정수를 의미하고, 정확히 $K$개의 그렇고 그런 사이가 만들어져야 한다.

정확히 $K$개의 그렇고 그런 사이를 만들 방법은 항상 존재하고, 만약 여러 가지 방법이 있다면 그중 하나를 출력한다.

문제 풀이

1. 가장 큰 숫자부터 선택하며 합을 구한다.
2. 만약 현재 합이 K를 초과하면 다음으로 작은 숫자를 선택한다.
3. 위 과정을 반복한다.

핵심 과정은 위와 같다.

이를 참고하여 코드를 짜면 쉽게 풀수있다.

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        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 currentSum = 0;
        int currentIndex = N - 1;
        boolean[] selectedNumbers = new boolean[N];

        while (currentIndex > 0) {
            if (currentSum + currentIndex <= K) {
                currentSum += currentIndex;
                selectedNumbers[currentIndex] = true;
            }
            currentIndex--;
        }

        for (int i = N - 1; i >= 0; i--) {
            if (selectedNumbers[i]) {
                bw.write(Integer.toString(i + 1) + " ");
            }
        }
        for (int i = 0; i < N; i++) {
            if (!selectedNumbers[i]) {
                bw.write(Integer.toString(i + 1) + " ");
            }
        }

        bw.flush();
        bw.close();
    }
}

코드 풀이

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        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());

• N, K: 배열의 크기와 어떤 조건에 따라 선택할 수 있는 수를 입력받을 변수

        int currentSum = 0;
        int currentIndex = N - 1;
        boolean[] selectedNumbers = new boolean[N];

• currentSum: 현재까지 선택한 숫자들의 합을 나타내는 변수
• currentIndex: 현재 고려하는 숫자의 인덱스
• selectedNumbers: 선택된 숫자들을 표시하기 위한 논리 배열

        while (currentIndex > 0) {
            if (currentSum + currentIndex <= K) {
                currentSum += currentIndex;
                selectedNumbers[currentIndex] = true;
            }
            currentIndex--;
        }

• currentIndex가 0보다 클 경우, 현재까지의 합과 현재 숫자를 더했을 때 K보다 작거나 같다면, 해당 숫자를 선택한 것으로 표시하고 currentSum에 더하고, selectedNumbers를 true로 바꿔준다.
• currentIndex를 감소시켜 다음 숫자를 검사한다.

        for (int i = N - 1; i >= 0; i--) {
            if (selectedNumbers[i]) {
                bw.write(Integer.toString(i + 1) + " ");
            }
        }

• selectedNumbers 배열을 역순으로 검사하면서 선택된 숫자를 출력한다.
• 출력은 bw를 사용하고, 선택된 숫자의 인덱스에 1을 더해 실제 숫자로 변환하여 출력한다.

        for (int i = 0; i < N; i++) {
            if (!selectedNumbers[i]) {
                bw.write(Integer.toString(i + 1) + " ");
            }
        }

        bw.flush();
        bw.close();
    }
}

• 선택되지 않은 숫자들도 출력해준다.