[ 백준 11877 ] 홍수 (c/c++)

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

 

 

[ 문제 요약 ]

다음 3조건을 만족할 경우 물이 넘치지 않는다.

v1 = 0, vN = 0

vi > 0인 모든 2 이상의 i에 대해 hi + vi ≤ hi-1 + vi-1

vi > 0인 모든 1 ≤ i ≤ (N-1)인 i에 대해 hi + vi ≤ hi+1 + vi+1

N, X가 주어질 때, 용량이 X인 히스토그램을 만들 수 없다면 -1, 그렇지 않다면 히스토그램의 열의 높이를 출력한다.

 

 

[ 문제 풀이 ]

1. 용량의 최대값은 1부터 N-2까지의 합이므로 X의 값이 이보다 크다면 -1을 출력한다.

2. 만약 1부터 더하다가 합이 X보다 커질 경우 더 이상 더하지 않지고 그때의 값을 m에 넣는다.

3. 이후 합에서 0부터 m-1까지의 수를 빼다가 합에서 뺀 값이 X가 되는 값을 n에 넣는다.

4. 이후 n번째 값을 제외하고 N-1과 N 사이에 출력한다.

 

 

[ 소스 코드 ]

#include <bits/stdc++.h>
using namespace std;

long long N, X, m, n, sum = 0;

int main() {
    cin >> N >> X;
    for (int i=1; i<=N-2; i++){
        sum = sum + i;
        if (sum >= X){
            m = i;
            break;
        }
    }
    for (int i=0; i<m; i++){
        if (sum - i == X){
            n = i ;
            break;
        }
    }

    if (sum < X) cout << "-1";
    else {
        cout << N-1 << " ";
        for (int i=1; i<=m; i++){
            if (i == n) continue;
            cout << N-1-i << " ";
        }
        cout << N << " ";
        if (n) cout << N-1-n << " ";
        for (int i=m+1; i<=N-2; i++) cout << N-1-i << " ";    
    }
    return 0;
}

 

 

[ 주의할 점 ]

합을 구하는 과정을 거꾸로 되짚어 가면서 풀어야 한다.