백준 31066번 [비 오는 날](C++) -yes6686- 티스토리

백준 문제 풀이: 31066 [비 오는 날]

---

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

문제 설명:

주어진 조건을 바탕으로 물통을 이용해 물을 채우는 시뮬레이션을 진행하는 문제입니다. n은 총 물을 채워야 하는 양, m은 한 번에 사용할 수 있는 물통의 크기, k는 한 번에 사용할 수 있는 물통의 최대 개수를 나타냅니다.

다음 조건을 만족하며 물을 채우는 과정을 시뮬레이션하고 최소 횟수를 구하는 문제입니다:

• 각 물통은 m 크기이며, 한 번에 최대 k개의 물통을 사용할 수 있습니다.
• 필요한 물의 양 n을 모두 채울 때까지 작업을 반복합니다.
• 특정 조건(n > 1, m == 1, k == 1)에서는 불가능한 경우가 존재합니다.

---

문제 해결 코드

// C++로 구현된 코드
#include <iostream>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    int T;
    cin >> T; // 테스트 케이스 수
    while (T--) {
        int n, m, k;
        cin >> n >> m >> k;

        // 조건에 따라 불가능한 경우 처리
        if (n > 1 && m == 1 && k == 1) {
            cout << -1 << '\n';
            continue;
        }

        int cnt = 0;  // 작업 횟수
        int a = n, b = m, c = 0, d = 0; // 초기화
        while (true) {
            if (c == n) break; // 목표 달성 시 종료
            if (b == 0) { // 물통 비우기
                b = d;
                d = 0;
                c -= 1;
                a += 1;
            } else if (a >= b * k) { // 최대 물통 사용
                a -= b * k;
                d = b;
                c += b * k;
                b = 0;
            } else { // 남은 물로 바로 완료 가능
                c = n;
            }
            cnt++;
        }
        cout << cnt << '\n'; // 최소 작업 횟수 출력
    }
}

---

코드 설명

코드의 주요 로직과 사용된 알고리즘 설명.

• 핵심 알고리즘: 각 물통 크기와 최대 사용 개수를 활용해 물을 효율적으로 채우는 시뮬레이션 알고리즘.
• 구현 세부사항:
  • n, m, k의 조건을 초기 처리해 불가능한 상황을 제외합니다.
  • 물통을 채우거나 비우는 과정을 반복하며 목표에 도달할 때까지 시뮬레이션합니다.
• 시간 복잡도 분석:
  • 각 반복에서 물통 채우기와 비우기 작업은 상수 시간에 처리됩니다.
  • 전체 작업 횟수는 대략적으로 O(n / (m⋅k))에 비례합니다.

---

결과

입력된 테스트 케이스마다 최소 작업 횟수를 정확히 계산합니다.

해당 문제에 대한 다른 접근 방식이나 개선 사항이 있다면 댓글로 공유 부탁드립니다!