[백준 / BOJ] 1060 좋은 수 (CPP)

문제

출처 : https://www.acmicpc.net/problem/1060

1060번: 좋은 수

정수 집합 S가 주어진다. 이때 다음 두 조건을 만족하는 범위[A,B]의 갯수가 적을수록 좋은 수 라고 한다.

• A와 B는 양의 정수이고, A < B를 만족한다.
• A ≤ x ≤ B를 만족하는 모든 정수 x가 집합 S에 속하지 않는다.

이때, 좋은 수 n개를 좋은 수 순서대로(같다면 작은 수를 먼저) 출력하는 문제다.

---

풀이

문제 이해만 되면 풀이 생각하기는 쉬운 문제였다.

정수 집합 S가 주어지면 집합 S안에 있는 수 들은 모두 가장 좋은 수 임이 확실하다. (집합의 정수가 범위에 포함된다면 범위를 정의할 수 없기 때문에...)

 

따라서, 집합 사이사이를 탐색해가며 좋은 수를 찾아줘야한다. 이건 예제를 같이 풀어보며 찾아보는게 더 빠를것이다.

문제의 입력으로 주어진 예제 2번을 보자.

 

3

5 11 18

9

양의 정수이므로, 가능한 범위는 다음과 같이 나온다.

A. 1 ~ 4

B. 6 ~ 10

C. 12 ~ 17

D. 19 ~ 무한대

이제 이 범위들을 탐색하며 좋은 수를 찾아야한다. A번 범위 먼저 탐색해보자.

n = 1 일 경우에 1을 포함하는 좋은 범위는 아래와 같이 나온다.

1 ~ 4

1 ~ 3

1 ~ 2

즉, 정수 1 의 좋은 범위는 3개이며, 1은 3만큼 좋은 수 이다.

 

n = 2 일 경우에 2를 포함하는 좋은 범위는 아래와 같이 나온다.

1 ~ 4

1 ~ 3

1 ~ 2

2 ~ 4

2 ~ 3

정수 2의 좋은 범위는 5개 이며, 2는 5만큼 좋은 수 이다.

 

이렇게 모든 범위를 찾아주면된다.

(단, A ~ 무한대 인 범위는 좋은 범위가 무한대로 나오므로 굳이 탐색하지 않고 앞에서 부터 출력해도 된다.)

하지만 이런식으로 매 정수마다 좋은 범위를 찾아주면 시간초과가 날 수도 있다.

예를들어 최악의 경우

1

1,000,000,000

100

인 경우에 탐색해야 하는 범위는 2 ~ (1,000,000,000-1) 이 되는데, 범위를 하나씩 줄여갈경우 1,000,000,000 / 2 만큼 반복할 것 이기 때문이다.

 

따라서, 문제를 풀기 위해서 범위에 따른 좋은 범위의 증감 규칙을 찾아줘야했다.

시간제한안에 문제를 푸느라 증명은 하지 못했지만, 직접 범위의 갯수를 그려보면 쉽게 파악이 가능한데,

범위가 1 ~ 10인 경우를 손으로 그려보며 해보자.

그러면 첫번째 숫자(1)와 마지막숫자(10)의 좋은 범위의 갯수는 (오른쪽 범위) - (왼쪽범위) = 10 - 1 = 9 가 된다.

두번째 숫자(2)와 9번째 숫자(9)의 좋은 범위의 갯수는 (첫번째 숫자의 좋은 범위 갯수) + ((오른쪽 범위) - (왼쪽 범위)-2) = 9 + 9 - 2 = 16 이 된다.

세번째 숫자(3)와 8번째 숫자(8)의 좋은 범위의 갯수는 (두번째 숫자의 좋은 범위 갯수) + ((오른쪽 범위) - (왼쪽 범위)-4) = 16 + 9 - 4 = 21이 된다.

이 과정을 중간값 5 까지 반복하며 좋은숫자를 찾아 저장하고 정렬 후 출력하면 된다.

 

주요 소스코드

void findGoodNums(long long left, long long right){
    long long rangeCount = right - left;
    long long inc = rangeCount-1;
    long long pushCount = 0;
    for(long long i = 0; i <= (left + right) / 2; i++){
        if(pushCount > S || right - i < left + i) break;
        goodNums.push_back({rangeCount, left + i});
        pushCount++;
        if(right - i != left + i){
            goodNums.push_back({rangeCount, right - i});
            pushCount++;
        }
        rangeCount += inc;
        inc -= 2;
    }
}

left 와 right 범위를 입력받은 후 좋은 수를 찾아 저장하는 함수이다.

 

문제를 풀때 주의해야할 점이 몇가지 있었는데

1. 연산중 int범위를 초과할 수 있다.

2. 입력으로 주어지는 집합이 정렬된 상태로 주어지는것 이 아니다.

3. 집합 S가 항상 가장 좋은 수 인것은 아니다. 예를들어 다음과 같은 입력에서는 1 2 3 이 출력되어야 한다.

2

2 3

3

---

소스코드

https://github.com/devxb/JJUNalgo/blob/master/1060%20좋은%20수/main.cpp

GitHub - devxb/JJUNalgo: 백준 알고리즘 소스코드🙃