BOJ 1703 - 생장점

문제

BOJ 1703 - 생장점

나무의 생장 과정이 주어진다. 매 단계마다 각 생장점이 a개로 분화하고, 바람에 b개가 꺾인다. N단계 후 남은 생장점 수를 구하라.

입력

여러 테스트 케이스가 주어진다. 각 줄의 첫 수가 N이고 이후 a, b 쌍이 N개 주어진다. N이 0이면 종료.

출력

각 테스트 케이스마다 남은 생장점 수를 출력한다.

예제

풀이

초기 생장점 1개에서 시작하여 각 단계마다 a를 곱하고 b를 빼는 단순 시뮬레이션이다.

1. 생장점 수를 1로 초기화한다
2. N단계를 반복하며 각 단계에서 cnt = cnt * a - b를 계산한다
3. 최종 생장점 수를 출력한다
4. 입력의 N이 0이 될 때까지 반복한다

핵심 아이디어: 각 단계의 연산이 독립적이므로 순서대로 곱셈과 뺄셈을 적용하면 O(N)에 해결된다.

코드

#include <bits/stdc++.h>
 
using namespace std;
 
int main()
{
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  cout.tie(nullptr);
 
  while (1)
  {
    int n, a, b, cnt = 1;
 
    cin >> n;
 
    if (n == 0)
      break;
 
    while (n--)
      cin >> a >> b, cnt *= a, cnt -= b;
 
    cout << cnt << '\n';
  }
 
  return 0;
}

복잡도

• 시간: O(N) (N: 단계 수)
• 공간: O(1)