BOJ 1233 - 주사위

문제

면이 S1, S2, S3개인 세 주사위를 던질 때, 세 눈의 합 중 가장 자주 나오는 값을 구하라.

입력

S1, S2, S3가 공백으로 주어진다 (각각 6 이하).

출력

가장 자주 나오는 합을 출력한다. 여러 개면 가장 작은 값을 출력한다.

예제

입력	출력
`3 3 3`	`6`

풀이

세 주사위의 모든 경우의 수를 탐색하여 합의 빈도를 구한다.

삼중 반복문으로 모든 (i, j, k) 조합의 합을 구한다
각 합의 빈도를 배열에 기록한다 (100에서 빼는 방식으로 카운팅)
배열에서 가장 작은 값(= 가장 많이 등장)의 인덱스를 출력한다

핵심 아이디어: S1, S2, S3가 각각 최대 6이므로 최대 216가지 경우만 탐색하면 된다.

코드

package day799;
 
import java.io.*;
import java.util.*;
 
public class Day758BOJ1233주사위 {
  public static void main(String[] args) throws Exception {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
 
    String[] nums = br.readLine().split(" ");
    int s1 = Integer.parseInt(nums[0]);
    int s2 = Integer.parseInt(nums[1]);
    int s3 = Integer.parseInt(nums[2]);
    int[] result = new int[s1 + s2 + s3 + 13];
    Arrays.fill(result, 100);
    for (int i = 1; i <= s1; i++) {
      for (int j = 1; j <= s2; j++) {
        for (int k = 1; k <= s3; k++) {
          result[i + j + k]--;
        }
      }
    }
    int min = 100;
    int idx = -1;
    for (int n = 0; n < result.length; n++) {
      if (min > result[n]) {
        min = result[n];
        idx = n;
      }
    }
    System.out.println(idx);
  }
}

복잡도

시간: O(S1 * S2 * S3) — 최대 216
공간: O(S1 + S2 + S3) — 합 빈도 배열

문제