[코드트리/INTERMEDIATE LOW] 1차원 윷놀이 (JAVA)

📖 문제

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

 

 

💡  풀이 방식

• 백트래킹

1. 말 K개 中 N개를 뽑는 재귀함수를 작성한다.

2. 말을 N개 뽑았을 때, 해당 순열에서 말을 이동시켜본다.

3. 말 위치가 윷놀이 판 상태보다 크거나 같은 값에 위치한다면, 정답 + 1한다.

4. 3에서 구한 정답과 최댓값을 비교해 더 큰 값으로 갱신한다.

 

 

💥 유의사항

N번 턴을 다 끝마치지 못하고 최대 점수를 얻을 수 있으므로,

모든 턴에 대해 점수를 계산해 그 중 최댓값을 계산해야 한다.

 

 

🔺 코드

import java.util.*;
import java.io.*;
 
public class Main {
    static int N, M, K;
    static int[] turns;     // 턴 수 배열
    static int[] moveArr;   // 말 위치 배열
    static int[] arr;       // 순열 배열
 
    static int answer;    
 
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
 
        N = Integer.parseInt(st.nextToken());   // 턴 수
        M = Integer.parseInt(st.nextToken());   // 윷놀이 판 상태
        K = Integer.parseInt(st.nextToken());   // 말 수
 
        turns = new int[N ];
        st = new StringTokenizer(br.readLine(), " ");
        for(int i = 0 ; i < N ; i++) {
            turns[i] = Integer.parseInt(st.nextToken());
        }
        
        arr = new int[N];
        perm(0);
 
        System.out.println(answer);
    }
 
    // 말 K개 中 N개 뽑는 순열 (백트래킹)
    private static void perm(int cnt) {
        if(cnt == N) {
            calculate();
            return;
        }
 
        for(int i = 1 ; i <= K ; i++) {
            arr[cnt] = i;
            perm(cnt + 1);
        }
    }
 
    // 턴에 대해 점수를 계산하고 그 중 최댓값 계산
    private static void calculate() {
        int score = 0;
        moveArr = new int[K + 1];
 
        for(int i = 0 ; i < N ; i++) {
            moveArr[arr[i]] += turns[i];
        }
 
        for(int i = 1 ; i <= K ; i++) {
            if(moveArr[i] >= M - 1) {
                score++;
            }
        }
 
        answer = Math.max(answer, score);
    }
}

 

 

 

 

➕ 다른 풀이 방식

import java.util.*;
import java.io.*;
 
public class Main {
    static int N, M, K;
    static int[] nums;        // 턴 수 배열
    static int[] pieces;    // 말 위치 배열
 
    static int answer;    
 
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
 
        N = Integer.parseInt(st.nextToken());   // 턴 수
        M = Integer.parseInt(st.nextToken());   // 윷놀이 판 상태
        K = Integer.parseInt(st.nextToken());   // 말 수
 
        nums = new int[N];
        st = new StringTokenizer(br.readLine(), " ");
        for(int i = 0 ; i < N ; i++) {
            nums[i] = Integer.parseInt(st.nextToken());
        }
        
        // 모든 말들의 초기 위치는 1에서 시작
        pieces = new int[K];
        for(int i = 0 ; i < K ; i++) {
            pieces[i] = 1;
        }
 
        findMax(0);
 
        System.out.println(answer);
    }
 
    private static void findMax(int cnt) {
        // 🔔 말을 직접 n번 움직이지 않아도 최대가 될 수 있으므로 항상 답 갱신
        answer = Math.max(answer, calc());
 
        if(cnt == N) {
            calc();
            return;
        }
 
        for(int i = 0 ; i < K ; i++) {
            // (조건) 움직여서 더 이상 이득이 안 된다면, 더 이상 움직이지 않음
            if(pieces[i] >= M)  continue;
 
            pieces[i] += nums[cnt];
            findMax(cnt + 1);
            pieces[i] -= nums[cnt];
        }
    }
 
    // 점수 계산 메소드
    private static int calc() {
        int score = 0;
        for(int i = 0 ; i < K ; i++) {
            score += (pieces[i] >= M ? 1 : 0);
        }
 
        return score;
    }
}

 

---

💦 어려웠던 점

- 필요한 자료구조를 사전에 생각해둬야겠다. 필요한 자료구조를 머릿속으로만 생각하려니 헷갈린다.

- 메소드를 따로 분리할 생각을 하다 보니 그냥 코드 작성 자체를 머뭇거리게 되는데 일단 다 넣어놓고 그 담에 따로 분리할 생각을 해야겄다...

 

 

1회독	2회독	3회독	4회독	5회독
V

---

(참고)

코드트리_1차원 윷놀이