KOI 2016 전국대회 초등부

1. 방 배정

---

https://www.acmicpc.net/problem/13300

학생들을 학년별, 성별로 한 방에 배정하려고 하는데 필요한 최소 방의 개수를 구하는 문제다. 문제에서 요구하는 대로 학년별, 성별로 인원을 센 다음에 각각에 대해 최소로 필요한 방의 개수를 센 뒤 더해주면 된다. 이는 나눗셈과 나머지 연산으로 쉽게 구할 수 있다.

#include <stdio.h>

int n, k, s, y, C[7][2];

int main() {
  scanf("%d%d", &n, &k);
  while (n--) {
    scanf("%d%d", &s, &y);
    ++C[y][s];
  }
  
  int ans = 0;
  for (int i = 1 ; i <= 6 ; ++i) {
    for (int j = 0 ; j < 2 ; ++j) {
      int cnt = C[i][j];
      ans += cnt / k + (cnt % k ? 1 : 0);
    }
  }
  printf("%d\n", ans);
}

2. 타일 장식물

---

https://www.acmicpc.net/problem/13301

위 그림과 같은 규칙으로 타일을 붙여 나갈 때 \(n\)번 째 타일을 붙이고 난 뒤 생긴 직사각형의 둘레를 출력하는 문제다. 문제를 잘 보면 \(n\)번 째 타일의 크기는 점화식 \(dp[n]=dp[n-1]+dp[n-2]\)으로 정의되는 것을 알 수 있다. 이렇게 모든 순서의 타일 크기를 알아내면  전체 직사각형의 둘레를 쉽게 구할수 있다. 답을 구하는 식은 아래와 같다.

\(ans = dp[n] \times 4 + dp[n-1] \times 2\)

왜 그런지는 잘 생각해보면 알 수 있다. 

#include <stdio.h>

typedef long long ll;

int n;
ll dp[81];

int main() {
  scanf("%d", &n);
  
  dp[1] = dp[2] = 1;
  for (int i = 3 ; i <= n ; ++i) {
    dp[i] = dp[i - 1] + dp[i - 2];
  }
  ll ans = dp[n] * 4LL + dp[n - 1] * 2LL;
  printf("%lld\n", ans);
}

(리조트, 장애물 경기 업로드 예정)