이 문제에서는 세 개의 정수 N, A, B가 주어집니다. 좌표 0에 서 있는 사람이 오른쪽으로 A걸음, 다시 왼쪽으로 B걸음씩 이동하는 동작을 반복합니다. 즉, 첫 번째 이동은 오른쪽, 두 번째 이동은 왼쪽, 세 번째 이동은 다시 오른쪽으로 진행되며, 우리의 목표는 N번 이동 후 사람의 최종 위치를 출력하는 것입니다.
문제 예시
예제를 통해 문제를 자세히 살펴보겠습니다.
- 입력: N = 4, A = 3, B = 1
- 출력: 4
1번째 이동 → 오른쪽 3걸음 (+3)
2번째 이동 → 왼쪽 1걸음 (-1)
3번째 이동 → 오른쪽 3걸음 (+3)
4번째 이동 → 왼쪽 1걸음 (-1)
4번 이동 후 위치: +3 − 1 + 3 − 1 = 4
접근 방법
이 문제를 해결하려면 사람이 이동한 총 거리를 계산해야 하며, 이때 오른쪽 이동은 양수(+), 왼쪽 이동은 음수(−)로 처리합니다. 핵심 규칙은 다음과 같습니다.
- 홀수 번째 이동(1, 3, 5, ...)은 항상 오른쪽으로 A걸음 이동합니다.
- 짝수 번째 이동(2, 4, 6, ...)은 항상 왼쪽으로 B걸음 이동합니다.
N번의 이동 중 오른쪽으로 이동하는 횟수는 (N+1)/2회이고, 왼쪽으로 이동하는 횟수는 N/2회입니다(C++의 정수 나눗셈 특성 활용). 따라서 최종 위치는 다음 공식 하나로 간단히 계산할 수 있습니다.
최종 위치 = ((N + 1) / 2) × A − (N / 2) × B
이 공식을 사용하면 반복문 없이도 상수 시간 O(1) 안에 답을 구할 수 있습니다.
C++ 구현 예제
위 접근 방식을 구현한 프로그램은 다음과 같습니다.
#include <iostream>
using namespace std;
void finalPosition(int n, int a, int b) {
int steps = ((n + 1) / 2) * a - (n / 2) * b;
cout << steps;
}
int main() {
int N = 4, A = 3, B = 1;
cout << N << "번 이동 후 사람의 최종 위치는 ";
finalPosition(N, A, B);
return 0;
}
실행 결과
4번 이동 후 사람의 최종 위치는 4
동작 원리 살펴보기
N = 4, A = 3, B = 1인 경우를 공식에 대입해 보면 다음과 같습니다.
- 오른쪽 이동 횟수: (4 + 1) / 2 = 2회 → 2 × 3 = +6
- 왼쪽 이동 횟수: 4 / 2 = 2회 → 2 × 1 = −2
- 최종 위치: 6 − 2 = 4
결과가 앞서 단계별로 계산한 값과 일치하는 것을 확인할 수 있습니다.
복잡도 분석
- 시간 복잡도: O(1) — 단순 산술 연산만 수행합니다.
- 공간 복잡도: O(1) — 추가 메모리를 사용하지 않습니다.