백준 32642번 [당구 좀 치자 제발](C++) -yes6686- 티스토리

 

백준 문제 풀이: 32642 [당구 좀 치자 제발]

---

문제 링크: https://www.acmicpc.net/problem/32642

문제 설명:

동우는 당구를 치고 싶지만, 수호는 비가 오면 집 밖에 나가지 않습니다. 그래서 비 오는 날엔 동우는 당구를 칠 수 없어 분노가 쌓입니다. 분노는 비 오는 날에 1 증가하고, 비가 오지 않으면 1 감소합니다. 단, 분노는 음수가 될 수 없으며 항상 0 이상입니다.

당신은 N일 동안의 비 정보를 보고, 동우가 겪게 될 분노 수치를 1일부터 N일까지 누적하여 더한 값을 출력해야 합니다.

---

문제 해결 코드

#include <stdio.h>

int main() {
    int n;
    scanf("%d", &n);

    long long int ans = 0;
    int k = 0;

    for (int i = 0; i < n; i++) {
        int x;
        scanf("%d", &x);
        if (x == 0) {
            k = (k > 0) ? k - 1 : 0; // 분노 감소 (음수 방지)
        } else {
            k++; // 분노 증가
        }
        ans += k; // 누적 분노 합계
    }

    printf("%lld", ans);
    return 0;
}
  

---

코드 설명

• 핵심 알고리즘: 시뮬레이션. 매일 비가 오는지 안 오는지를 확인하여 분노 수치를 조절하고 누적합을 구합니다.
• 구현 세부사항:
  • 비가 오는 날은 x == 1일 때 분노 수치 k를 1 증가시킵니다.
  • 비가 오지 않는 날은 x == 0일 때 분노 수치 k를 1 감소시키되, 0 미만으로 내려가지 않게 합니다.
  • 매일의 분노 수치 k를 누적하여 ans에 더합니다.
• 시간 복잡도 분석: O(n) — 입력을 한 번 순회하면서 처리하기 때문에 효율적입니다.

---

결과

예시 입력:

입력:
8
1 1 0 1 0 0 1 0

출력:
8

분노 수치의 변화: 1 → 2 → 1 → 2 → 1 → 0 → 1 → 0 → 합계 = 8

동우의 누적 분노 합을 잘 구해 화병을 예방해 줍시다!

다른 아이디어나 최적화 방식이 있다면 댓글로 남겨주세요 :)