백준 21557번 [불꽃놀이](C++) -yes6686- 티스토리

백준 문제 풀이: 21557 [불꽃놀이]

---

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

문제 설명:

불꽃놀이가 진행되는 과정에서 좌표상에서 위치 s와 e가 주어질 때, 두 지점 사이의 거리를 줄이고 남은 이동 횟수를 반으로 분배하여 중심점으로 이동합니다. 가능한 최종 좌표를 계산하는 문제입니다.

---

문제 해결 코드

// 백준 21557 - 불꽃놀이
#include <iostream>
using namespace std;

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

    int n;
    cin >> n; // 좌표의 개수
    int s, e;

    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;
        if (i == 0) s = x; // 시작 위치
        if (i == n - 1) e = x; // 끝 위치
    }

    s--; e--; // 0-based 인덱스로 조정
    int remainingMoves = n - 3; // 남은 이동 횟수

    if (s > e) {
        int distance = s - e;
        if (remainingMoves >= distance) {
            remainingMoves -= distance;
            s = e;
            cout << max(0, s - remainingMoves / 2) << '\n';
        } else {
            s -= remainingMoves;
            cout << s << '\n';
        }
    } else {
        int distance = e - s;
        if (remainingMoves >= distance) {
            remainingMoves -= distance;
            e = s;
            cout << max(0, e - remainingMoves / 2) << '\n';
        } else {
            e -= remainingMoves;
            cout << e << '\n';
        }
    }

    return 0;
}

---

코드 설명

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

• 핵심 알고리즘:
  • 시작 위치 s와 끝 위치 e 간의 거리를 줄이고, 남은 이동 횟수를 반으로 나누어 양방향 이동합니다.
• 구현 세부사항:
  • distance: 시작과 끝 위치의 차이를 계산합니다.
  • 남은 이동 횟수가 거리보다 많거나 같으면 중심으로 이동하며, 그렇지 않으면 한 방향으로 이동합니다.
  • max(0, ...)를 사용하여 결과 좌표가 음수가 되지 않도록 합니다.
• 시간 복잡도 분석:
  • 입력 및 기본 연산: O(n)
  • 최종 계산: O(1)
  • 총 시간 복잡도: O(n)

---

결과

제출 시, 모든 테스트 케이스에 대해 올바른 결과를 출력합니다.

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