BOJ 4922 - Walk Like an Egyptian

문제

BOJ 4922 - Walk Like an Egyptian

고대 이집트에서 수를 표현하는 방식을 시뮬레이션하는 문제이다. 자연수 N이 주어졌을 때, 이집트 숫자 표현에 사용된 기호 개수의 합을 구한다.

이집트 수 표현에서 각 자릿수 기호의 개수는 해당 자릿값을 가장 큰 단위 기호부터 순서대로 나타낸다. 코드의 동작을 분석하면, 1, 3, 5, 7, ... 처럼 홀수 번째 항들의 합을 구하되 결과에서 N-1을 빼는 형태로 계산한다. 이는 1 + 3 + 5 + ... + (2N-1) = N^2에서 파생된 변형 공식이다.

입력

• 여러 개의 테스트 케이스가 주어진다.
• 각 줄에 정수 N이 주어진다. (N = 0이면 종료)

출력

각 테스트 케이스에 대해 N => result 형식으로 결과를 출력한다.

예제

풀이

N이 주어지면 1부터 시작해 2씩 증가하는 수열의 첫 N개 항을 합산한 뒤, N-1을 빼어 정답을 구한다.

1. 0이 입력될 때까지 반복한다.
2. cnt를 1로 초기화하고, N번 반복하며 sum += cnt, cnt += 2를 수행한다.
3. 결과는 sum - n + 1로 출력한다.

핵심 아이디어: 1, 3, 5, ..., (2N-1)의 합은 N^2이다. 코드에서는 sum - n + 1로 이를 계산하는데, sum = N^2이고 최종 답은 N^2 - N + 1이 된다.

코드

#include <iostream>
using namespace std;
int main()
{
  while (1)
  {
    int n, sum = 0, cnt = 1;
    cin >> n;
    if (!n)
      break;
    for (int i = 0; i < n; i++, cnt += 2)
      sum += cnt;
    cout << n << " => " << sum - n + 1 << '\n';
  }
}

복잡도

• 시간: O(N) — 테스트 케이스당 N번 반복
• 공간: O(1) — 상수 개의 변수만 사용