백준 1592번 [영식이와 친구들](C++) -yes6686- 티스토리

백준 문제 풀이: 1592 (영식이와 친구들)

---

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

문제 설명:

N명의 친구들이 원형으로 앉아 공을 던집니다. 공을 M번 받은 사람이 나오면 게임이 끝납니다. 공을 받은 횟수가 **홀수**면 오른쪽으로 L번째, **짝수**면 왼쪽으로 L번째 친구에게 공을 던집니다. 공을 던지는 총 횟수를 구하세요.

---

문제 해결 코드

#include <iostream>
using namespace std;

int arr[51]; // 각 친구의 공을 받은 횟수

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

    int n, m, l; // n: 친구 수, m: 게임 종료 조건(최대 횟수), l: 던지는 거리
    cin >> n >> m >> l;

    int i = 1;   // 현재 공을 가진 사람 (1번부터 시작)
    int cnt = -1; // 공을 던진 횟수 (-1부터 시작해서 초기 던지기를 포함)

    while (true) {
        arr[i]++; // 현재 사람이 공을 받음
        cnt++;    // 공을 던진 횟수 증가

        // 게임 종료 조건: 공을 M번 받은 사람이 나오면 종료
        if (arr[i] >= m) {
            break;
        }

        // 다음 사람을 결정: 홀수면 오른쪽, 짝수면 왼쪽
        if (arr[i] % 2 == 0) { 
            i -= l; // 짝수면 왼쪽으로 던짐
            if (i <= 0) { 
                i += n; // 원형 구조로 돌아감
            }
        } else { 
            i = (i + l - 1) % n + 1; // 홀수면 오른쪽으로 던짐 (원형 구조 처리)
        }
    }

    cout << cnt << '\n'; // 총 던진 횟수 출력
    return 0;
}

---

코드 설명

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

• 게임 진행: 각 친구는 공을 받을 때마다 횟수가 증가합니다. 공을 M번 받은 친구가 나오면 게임이 종료됩니다.
• 원형 구조 처리:
  • 왼쪽으로 이동할 때: i -= l로 계산 후, i <= 0인 경우 i += n로 돌아갑니다.
  • 오른쪽으로 이동할 때: i = (i + l - 1) % n + 1를 사용해 원형 구조를 유지합니다.
• 시간 복잡도 분석: 각 공을 던질 때마다 O(1)의 연산을 수행하므로 총 O(공 던진 횟수)입니다. 게임은 최대 M번 공을 받을 때 종료되므로 **시간 복잡도는 O(N * M)**입니다.

---

결과

게임이 종료될 때까지 공을 던진 횟수를 정확히 계산하여 출력합니다.

• 입력 예시:

  5 3 2

• 출력 예시:

  10

다른 접근 방식이나 개선 사항이 있다면 댓글로 공유 부탁드립니다!