[백준 C++] 6591, 9375번 이항 쇼다운, 패션왕 신혜빈

이항 쇼다운

언뜻 보면 쉬워 보이면서도 수상쩍은 조건이 있다. 입력되는 두 수는 $2^{31}-1$을 넘지 않으며, 정답이 $2^{31}$보다 작은 경우만 입력으로 주어진다고 한다. $2^{31}-1$은 int형 자료형이 가질 수 있는 최대치이다. int 자료형을 쓰도록 유도하는 함정이라고 생각한다. 하지만 계산 중에 나오는 값이 int 자료형의 범위를 넘을 수 있으며, 이런 경우는 오버플로우 되므로 틀린다고 나올 것이다. 그것만 빼고는 따로 주의할 점이 없다.

#include <iostream>
using namespace std;
typedef long long ll;
int main() {
 
  int n, k;
 
  while (1) {
    cin >> n >> k;
    if (n == 0) break;
    if(k > n - k) k = n - k;
    ll res = 1;
    for (int i = 1; i <= k; i++)
      res = res * (n - i + 1) / i;
    cout << res << '\n';
  }
  return 0;
}

패션왕 신혜빈

이 문제는 문제를 해결하는 데는 시간이 얼마 안걸렸다. 모자 두 개와 신발 세 개, 셔츠 두 개가 있다면 모자의 경우에는 모자를 쓰지 않는 경우, 첫 번째 모자를 쓰는 경우, 두 번째 모자를 쓰는 경우 이렇게 세 가지 경우의 수가 있다. 즉, 특정 의류가 N 개 있다면 그 의류를 선택하는 경우의 수는 입지 않는 경우도 포함해서 N + 1 개이다. 마지막으로 알몸으로 다니면 안되므로 -1을 해준다. 그럼 결과는 $((2 + 1) * (3 + 1) * (2 + 1)) - 1 = 35$이다.

개인적으로 string 을 입력받는 것이 힘들었다. 스페이스로 나뉜 두 개의 string 이 있으니 string 을 두 개 선언해서 하나씩 받고, 두 번째 스트링을 사용하면 되는데 그것을 떠올리는 데 너무 오래 걸렸다.  string 을 입력받는 문제는 모아서 나중에 정리 해야겠다.

vector 에 새로운 원소를 추가할 때 push_back 을 썼었는데 'Clang-Tidy: Use emplace_back instead of push_back'라는 권유(?) 메시지가 떠서 emplace_back 을 사용했다. 기능은 유사한 것으로 보이며, 세부적인 차이는 stl vector 를 배울 때 알아봐야겠다.

#include <iostream>
#include <utility>
#include <vector>
using namespace std;
int main() {
 
  cin.tie(NULL);
  ios::sync_with_stdio(false);
 
  int TC, n;
  cin >> TC;
 
  while (TC--) {
 
    // 벡터에는 string과 int로 이루어진 pair가 들어간다.
    // string은 의상 종류를 비교하기 위한 것이고, int는 그 의상이 몇 개 있는지 세기 위해서 있다.
    vector<pair<string, int>> v;
    cin >> n;
    int res = 1;
 
    while (n--) {
      string name, kind;
      // 중복인지 아닌지 나타내주는 것이다.
      // 기본 값은 false이며, 입력되는 kind가 벡터에 이미 존재하면 true로 바뀐다.
      bool dup = false;
 
      cin >> name >> kind;
      // vector가 비었다면 무조건 원소를 추가한다.
      if (v.empty()) v.emplace_back(make_pair(kind, 1));
      else {
        // vector가 비지 않았다면 벡터를 조회해 kind와 같은 이름을 가진 원소가 있는지 확인한다.
        // 있다면, dup는 true로 바꾸고, 해당 원소의 second 값에 1을 더한다.
        for (int i = 0; i < v.size(); i++) {
          if (v[i].first == kind) {
            dup = true;
            v[i].second++;
          }
        }
        // 만약 dup이 false라면, 즉 같은 이름을 가진 원소가 없다면 원소를 추가한다.
        if (!dup) v.emplace_back(make_pair(kind, 1));
      }
    }
 
    for (int i = 0; i < v.size(); i++) {
      res *= (v[i].second + 1);
    }
    // 알몸인 경우는 제외해야 하므로 1을 뺀다.
    cout << res - 1 << '\n';
 
    v.clear();
  }
  return 0;
}