[백준 9546] 3000번 버스

백준 9546 - 3000번 버스

백준 9546번

❓ 문제

문제 : n명의 승객을 태우고 있는 3000번 버스는 강화에서부터 김포를 지나 신촌까지 가는 좌석버스이다. 3000번 버스는 버스 정류장마다 문을 연다. 그리고 정류장마다 타고 있는 승객의 수의 정확히 절반과 반 명(0.5명)의 승객이 내린다. 총 k개의 정류장에서 승객이 내렸고 마지막 정류장에서 승객이 없었으며 누구도 다치지 않았다면 맨 처음 타고있던 승객은 몇명인가.

---

✏️ 풀이

문제에서 정류장 k의 수는 1 <= k <= 30 이라고 적혀있다.

정류장의 수가 많지 않기 때문에, 1~30에 해당하는 모든 승객의 수를 vector에 담아놓고, 필요할때 불러 쓰기로 생각을 하였다.

recursion밖에 생각이 나지 않았고, 이를 이용하여 문제를 해결했다.

먼저, 이 문제를 점화식으로 나타내보자.

f(1) = (0 + 0.5) * 2 = 1
f(2) = (f(1) + 0.5) * 2 = 3
f(3) = (f(2) + 0.5) * 2 = 7
…

이러한 식을 가지고 있다.

따라서, 이를 재귀함수로 나타내보면 아래와 같다.

int recursion(int n) {
  if (n == 1)
    return 1;
  else {
    return (recursion(n-1)+0.5)*2;    
  }
}

---

✔️ 정답 코드

#include <iostream>
#include <vector>

using namespace std;

vector<int> result;

int recursion(int n);

int main(void) {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);

  int n;
  cin >> n;

  for (int i=1; i<=30; i++) {
    result.push_back(recursion(i));
  }

  for (int i=0; i<n; i++) {
    int k;
    cin >> k;
    if (k==1)
      cout << 1;
    else {
      cout << result[k-1];
    }
    if (i != n-1)
      cout << "\n";
  }
  
  return 0;
}

int recursion(int n) {
  if (n == 1)
    return 1;
  else {
    return (recursion(n-1)+0.5)*2;    
  }
}

🔥 이렇게 푸는게 맞는지 검색을 해보니, n^2-1이라는 공식?이 있었다.
그렇다면.. pow를 이용하여 풀면 되겠다!
또한, k의 수가 적어서 memoization을 이용하진 않았다!