자바 - 백준 1101 / 카드 정리 1

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

골드4

풀이 방법

• 박스의 상태는 크게 세가지로 분류 할 수 있다
  1. 어떠한 색도 없는 경우
  2. 색이 한가지인 경우
  3. 색이 두가지 이상인 경우
• 1번의 경우 이동이 발생하지 않는다
• 2번의 경우 앞서 같은 색이 한가지 있었던 경우 이동이 발생한다 하지만 처음 나오는 종류의 색인 경우 이동할 필요가 없다.
• 3번의 경우, 모두 이동을 해야한다. 이 문제에서는 모든 색을 포함할 수 있는 조커 박스가 있기 때문에 그곳으로 이동하면 될 일이다.
• 이제 조커 박스를 선택하는 기준에 대해 생각해야 한다. 이건 문제에 힌트가 있었다. 같은 색을 가진 모든 카드가 조커 박스에 들어있는 것도 가능 , 조커 박스는 색이 다른 카드를 보관해도 된다.
  두 문장을 통해 조커 박스는 같은 색을 가진 모든 카드가 들어있는 경우, 색이 다른 카드들이 있는 경우 모두 있을 수 있다는 것을 눈치해야 한다. 따라서 조커 박스를 선택할 수 있는 기준은 없고, 각각의 박스 모두 조커 박스일 때를 고려해여 답을 구해야 한다는 뜻이다.
• 문제 이해도 중요하다.
  1. 한 박스에서 여러 색을 옮겨도 이동 1번으로 생각한다.
  2. 2번째 줄부터 각 박스마다 색 종류별 개수가 적혀 있다.
     1. 색 종류가 적혀있는게 아님!

코드

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

/**
* 백준 1101
* 카드 정리 1
* 골드4
* <https://www.acmicpc.net/problem/1101>
*/
public class Boj1101 {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int N = Integer.parseInt(st.nextToken()); // 박스 수
        int M = Integer.parseInt(st.nextToken()); // 색 종류 수

        int[][] boxes = new int[N][M];

        for(int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());

            for(int j = 0; j < M; j++) {
                boxes[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        int answer = 50;
        for(int joker = 0; joker < N; joker++) {
            int temp = 0; // 이동 횟수
            boolean[] visited = new boolean[M];

            for(int i = 0; i < N; i++) {
                if(i == joker)
                    continue;

                int cnt = 0; // 색 종류 수
                int color = -1; // 색 종류
                for(int j = 0; j < M; j++) {
                    if(boxes[i][j] != 0) {
                        cnt++;
                        color = j;
                    }
                }

                if(cnt == 1) {
                    if(visited[color])
                        temp++;
                    else
                        visited[color] = true;
                } else if(cnt > 1) {
                    temp++;
                }
            }

            answer = Math.min(answer, temp);
        }

        System.out.println(answer);
    }
}

느낀점

• 늘 생각하지만 그리디 문제는 눈치가 빠르고, 감이 좋으면 매우 쉽고, 그렇지 않으면 매우 어려운것 같다.