boj 10350 Banks

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

 

생애 첫 루비문제입니다.

애드혹 문제라서 그런지 백준 게시판이나 블로그에서 아이디어를 얻지 않았다면 절대 손도 못댈거같은 그런 문제였습니다..

 

제가 힌트를 얻은건 1 ~ N번째 수를 계속 이어붙였을 때 음수 누적합이 나오는 갯수를 구하는 것이었습니다.

사실상 문제의 모든것 이었습니다..

 

아무튼 저는 누적합으로 접근했고, 각 은행들은 원형으로 배치되어 있기때문에 1 ~ N이 아닌 1 ~ 2N의 누적합으로 구해줍니다.

그리고 1, 2, 3, ... N에서 시작하여 N개의 수를 계속 이어붙일 때의 누적합들 중에 음수가 몇번 나오는지 카운팅하면 그게 답입니다.

 

4
1 -2 -1 3

예시로 설명드리면

처음 1번부터 누적합을 쭉 구하면

1 -1 -2 1 / 2 0 -1 2 / 3 1 0 3

이렇게 되고, 음수의 갯수는 3개입니다.

그리고 이후에 배열을 계속 이어도 음수가 나오지 않습니다.

 

그 다음 2번부터 누적합을 구하면

x -2 -3 0 1 / -1 -2 1 2 / 0 -1 2 3

이렇게 되고, 음수의 갯수는 5개입니다.

 

다음 3번부터 누적합을 구하면

x x -1 2 3 1 / 0 3 4 2 / 1 4 5 3

이렇게 되고, 음수의 갯수는 1개입니다.

 

마지막 4번부터 누적합을 구하면

x x x 3 4 2 1 / 4 5 3 2 / 5 6 4 3

이렇게 되고, 음수의 갯수는 0개입니다.

위에서 구한 갯수들을 전부 더하면 9개가 됩니다.

 

이 과정에서 규칙을 하나 찾을 수 있습니다.

우선 문제에서 입력으로 주어지는 수를 모두 더하면 양수라고 했습니다.

그리고 각 시작 지점을 i번이라고 했을 때 i번부터 N개의 누적합은 무조건 양수입니다.

 

제가 4개씩 끊은 구간들을 보시면 1번 구간의 수들에서 +1한 값들이 2번 구간이 되어 있습니다.

그리고 2번 구간에서 +1를 하면 3번 구간이 됩니다.

그 +1은 배열의 전체 누적합이 되고, 음수의 갯수는 음수 누적합 / 전체 누적합이 되는것을 알 수 있습니다.

계산하면 실수가 나오기 때문에 double형으로 바꿔주셔야 하고, 나머지는 무조건 올림 연산을 해야합니다.

이 방식으로 접근하시면 로직 자체는 간단하게 구현하실 수 있습니다.

이 문제는 이 방식을 생각해내는것 자체가 정말 어렵다는 것을 느꼈습니다.

 

 

#include <iostream>
#include <cmath>
#define MAX 20001
using namespace std;
typedef long long ll;
 
int dp[MAX];
int N;
 
void init() {
    for (int i = 1; i <= (N << 1); i++) {
        dp[i] += dp[i - 1];
    }
}
 
void func() {
    init();
 
    ll ret = 0;
    for (int i = 1; i <= N; i++) {
        for (int j = i; j < N + i; j++) {
            if (dp[j] - dp[i - 1] >= 0) continue;
            ret += (ll)ceil((double)(-dp[j] + dp[i - 1]) / (double)(dp[N + i - 1] - dp[i - 1]));
        }
    }
    cout << ret << '\n';
}
 
void input() {
    cin >> N;
    for (int i = 1; i <= N; i++) {
        cin >> dp[i];
        dp[i + N] = dp[i];
    }
}
 
int main() {
    cin.tie(NULL); cout.tie(NULL);
    ios::sync_with_stdio(false);
 
    input();
    func();
 
    return 0;
}