BOJ 9288 - More Dice

문제

BOJ 9288 - More Dice

두 개의 6면체 주사위(눈 1~6)를 굴려서 합이 주어진 값 S가 되는 모든 조합 (a, b)를 오름차순으로 출력한다. 단 a <= b 조건을 만족하는 쌍만 출력한다.

입력

첫 번째 줄에 테스트 케이스 수 T가 주어진다. 각 테스트 케이스마다 합 S가 주어진다.

출력

각 테스트 케이스에 대해 Case i: 헤더를 출력하고, 합이 S인 주사위 조합 (a,b)를 오름차순으로 출력한다.

예제

풀이

첫 번째 주사위 값을 1부터 S/2까지 순회하며, 나머지가 유효한 주사위 눈(1~6)인지 확인한다.

1. T개의 테스트 케이스를 처리한다.
2. 각 케이스 헤더 Case i:를 출력한다.
3. 첫 번째 값 j를 1부터 S/2까지 순회한다.
4. 두 번째 값 S - j가 6보다 크면 건너뛴다(유효한 주사위 눈 범위 초과).
5. 조건을 만족하면 (j, S-j) 형식으로 출력한다.

핵심 아이디어: j <= S/2 조건으로 a <= b를 보장하고, S - j <= 6 조건으로 두 번째 주사위 눈의 유효 범위를 검증한다. 주사위 눈이 1~6이므로 각 케이스당 최대 6번만 반복하는 사실상 O(1) 알고리즘이다.

코드

#include <iostream>
 
using namespace std;
int t, sum;
int main()
{
  cin >> t;
  for (int i = 1; i <= t; i++)
  {
    cin >> sum;
    printf("Case %d:\n", i);
    for (int j = 1; j <= sum / 2; j++)
    {
      if (sum - j > 6)
        continue;
      printf("(%d,%d)\n", j, sum - j);
    }
  }
}

복잡도

• 시간: O(T) — 각 케이스당 최대 6회(주사위 눈 범위) 반복으로 사실상 O(1)
• 공간: O(1) — 추가 자료구조 없음