백준(BOJ) 28075 : 스파이 (실버3) / 자바(Java) 풀이

문제

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

3줄 요약

1. 이 문제는 N일 동안 A와 B 두 곳을 방문하는 모든 경우의 수를 구하는 문제로, 중복순열(Permutation with Repetition)을 활용하여 해결할 수 있습니다.
   1. 중복순열은 순서를 고려하며, 같은 요소를 여러 번 선택할 수 있는 경우의 수를 의미합니다.
   2. 이 문제에서는 각 일자마다 A 또는 B 중 하나를 선택하며, 이전에 선택한 장소와 같은 장소를 다시 선택할 수 있습니다.
2. 재귀 함수 recursiveSearch를 사용하여 중복순열을 생성하며, 각 경우에서 얻을 수 있는 진척도의 합을 계산합니다.
   1. 재귀 함수의 매개변수로는 현재 방문 중인 일자(day), 이전에 방문한 장소(prev), 현재까지 누적된 진척도(progress)가 사용됩니다.
   2. 기저 조건으로 N일 동안 방문이 완료되었을 때, 누적된 진척도 합이 M 이상인 경우 경우의 수를 증가시킵니다.
3. 최종적으로 모든 중복순열을 탐색한 후, 조건을 만족하는 경우의 수를 출력합니다.
   중복순열을 활용하여 모든 경우를 탐색함으로써 문제에서 요구하는 진척도 합이 M 이상이 되는 경우의 수를 정확히 계산할 수 있습니다.

코드

// package boj28075;

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws Exception {
        // System.setIn(new FileInputStream("src/input.txt"));
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        // N과 M 입력받기
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken()); // 일수
        M = Integer.parseInt(st.nextToken()); // 목표 진척도
        
        // A 장소의 진척도 입력받기
        A = new int[3];
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < 3; i++) {
            A[i] = Integer.parseInt(st.nextToken());
        }
        
        // B 장소의 진척도 입력받기
        B = new int[3];
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < 3; i++) {
            B[i] = Integer.parseInt(st.nextToken());
        }
        
        br.close();
        
        // 재귀를 활용한 경우의 수 계산
        recursiveSearch(0, -1, 0);
        
        // 결과 출력
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        bw.write(Integer.toString(count));
        bw.flush();
        bw.close();
    }
    
    public static int N; // 일수
    public static int M; // 목표 진척도
    public static int[] A; // A 장소의 진척도
    public static int[] B; // B 장소의 진척도
    public static int count = 0; // 경우의 수
    
    public static void recursiveSearch(int day, int prev, int progress) {
        // 기저 조건: N일 동안 방문한 경우
        if (day == N) {
            // 진척도 합이 M 이상인 경우 경우의 수 증가
            if (progress >= M) {
                count++;
            }
            return;
        }
        
        // 각 장소에 대해 재귀 호출
        for (int i = 0; i < 3; i++) {
            // 이전에 방문한 장소와 동일한 경우
            if (i == prev) {
                // A 장소 방문 (진척도 절반)
                recursiveSearch(day + 1, i, progress + A[i] / 2);
                // B 장소 방문 (진척도 절반)
                recursiveSearch(day + 1, i, progress + B[i] / 2);
            } else {
                // A 장소 방문 (진척도 전체)
                recursiveSearch(day + 1, i, progress + A[i]);
                // B 장소 방문 (진척도 전체)
                recursiveSearch(day + 1, i, progress + B[i]);
            }
        }
    }
}