[백준/Java] 10350 : Banks

📌 문제 정보

• 번호: 10350
• 제목: Banks
• 난이도: Ruby 5
• 분류: 수학, 애드 혹, 누적 합, 불변량 찾기

---

💡 접근 방식

백준 서버 종료 전에 마지막으로 루비 문제 한 번은 풀어보고 싶어서 도전. 마법 이체가 "음수만큼 가져와 다시 분배"하는 구조라 전체 합이 바뀌지 않는 불변량부터 잡고 시작. 수식만으로는 안 풀려서 작은 케이스 BFS로 정답을 구해놓고, 입력 배열의 누적합과 정답 사이의 패턴을 노가다로 매칭한 끝에 "각 시작점 i에서 음수 부분합마다 ⌈|PS| / T⌉를 더한다"는 규칙을 발견

---

🔹 단계별 풀이

1단계 – 불변량: 전체 합은 보존됨

ki = -x (x > 0)에서 마법 이체 1회 후

ki  : -x → +x         (변화량 +2x)
이웃: 각각 -x          (변화량 -x씩, 합쳐 -2x)

세 칸의 합 변화는 0, 따라서 모든 은행의 합 T는 영원히 그대로. 문제 조건상 T > 0이 보장되므로, 충분히 마법을 쓰면 반드시 모두 0 이상으로 수렴 가능

---

2단계 – "시작점 → 누적합" 모델

원형 위 임의의 시작점 i에서 시계방향으로 부분합을 쌓아갈 때, 부분합이 음수로 빠지는 깊이가 곧 그 구간에서 채워야 할 부족분. 한 바퀴 합이 T이므로 깊이 |PS|를 메우려면 ⌈|PS| / T⌉ 회의 이체가 시작점 i에 청구됨. 이 값을 모든 시작점 i, 모든 j에 대해 합산한 게 정답

예시 (N=4, A = [1, -2, -1, 3], T = 1)

2배 복제: [1, -2, -1, 3, 1, -2, -1, 3]
누적합 dp[1..8]: [1, -1, -2, 1, 2, 0, -1, 2]

시작 i	부분합 PS_j (j=i..i+N-1)	음수만 ⌈/T⌉	기여
1	1, -1, -2, 1	1, 2	3
2	-2, -3, 0, 1	2, 3	5
3	-1, 2, 3, 1	1	1
4	3, 4, 2, 1	(없음)	0

총합 9 → 예제 정답 일치

---

3단계 – 원형 처리는 배열 2배 복제

매 시작점마다 인덱스 wrap-around를 따로 계산하면 코드가 지저분해짐. 입력을 2N 길이로 복제해 누적합을 한 번만 만들어두면, 시작점 i에서 j까지의 부분합은 dp[j] - dp[i-1]로 O(1)에 추출 가능

---

4단계 – 자료형은 long

N=9999, |ki|=32000 근방의 최악 입력에서 결과는 long 범위까지 도달. int로 두면 조용히 오버플로우

---

💻 핵심 코드

long[] dp = new long[2 * N + 1];
for (int i = 1; i <= N; i++) {
    int v = Integer.parseInt(st.nextToken());
    dp[i] = v;
    dp[i + N] = v;
}
for (int i = 1; i <= 2 * N; i++) {
    dp[i] += dp[i - 1];
}

long T = dp[N];
long ret = 0;
for (int i = 1; i <= N; i++) {
    long base = dp[i - 1];
    for (int j = i; j < N + i; j++) {
        long ps = dp[j] - base;
        if (ps >= 0) continue;
        long neg = -ps;
        ret += (neg + T - 1) / T;
    }
}
System.out.println(ret);

---

⏳ 복잡도 분석

• 시간 복잡도: O(N²)
  • 시작점 N개 × 길이 N 윈도우, N=9999에서 약 1억 연산이지만 단순 산술이라 0.2초대 통과
• 공간 복잡도: O(N)
  • 2N 길이 누적합 배열 한 개

---

📄 전체 코드

package rtaeho.week04.B10350;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine().trim());
        StringTokenizer st = new StringTokenizer(br.readLine());

        long[] dp = new long[2 * N + 1];
        for (int i = 1; i <= N; i++) {
            int v = Integer.parseInt(st.nextToken());
            dp[i] = v;
            dp[i + N] = v;
        }
        for (int i = 1; i <= 2 * N; i++) {
            dp[i] += dp[i - 1];
        }

        long T = dp[N];

        long ret = 0;
        for (int i = 1; i <= N; i++) {
            long base = dp[i - 1];
            for (int j = i; j < N + i; j++) {
                long ps = dp[j] - base;
                if (ps >= 0) {
                    continue;
                }
                long neg = -ps;
                ret += (neg + T - 1) / T;
            }
        }

        System.out.println(ret);
    }
}