[백준 16561] 3의 배수 (C#, C++) - soo:bak

문제 링크

16561번 - 3의 배수

설명

3의 배수 자연수 n을 세 개의 3의 배수 자연수 합으로 나타낼 때, 서로 다른 순서를 다른 방법으로 세어 총 경우의 수를 구하는 문제입니다.

접근법

n을 3으로 나눈 값을 m이라 두면, 문제는 m을 양의 정수 세 개의 합으로 만드는 조합 개수를 묻는 것으로 바뀝니다. 이는 순서를 구분하는 세 양수 분할이므로 해의 개수는 조합 공식 C(m-1, 2)와 같습니다. m-1개의 구분선 중 두 곳을 선택해 세 구간을 만드는 방식으로 생각하면 됩니다.

직접 이중 반복문으로 세어도 m이 최대 1000이므로 충분히 통과하지만, 조합 한 번으로 O(1)에 답을 얻을 수 있습니다.

---

Code

C#

using System;

class Program {
  static void Main() {
    var n = int.Parse(Console.ReadLine()!);
    var m = n / 3;
    var ans = (m - 1) * (m - 2) / 2;
    Console.WriteLine(ans);
  }
}

C++

#include <bits/stdc++.h>
using namespace std;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  int n; cin >> n;
  int m = n / 3;
  int ans = (m - 1) * (m - 2) / 2;
  cout << ans << "\n";

  return 0;
}