BOJ 1101 - 카드 정리 1

문제

N개의 박스에 M개의 색상([1, M])으로 구분되는 카드들을 넣어야 한다.
이때 아래와 같은 조건을 만족해야 한다.

1. 최대 1개의 박스를 조커 박스로 지정할 수 있고, 조커 박스는 색이 다른 카드들을 보관해도 된다.
2. 조커 박스를 제외한 모든 박스는 비어있거나, 같은 색의 카드만 보관해야 한다.
3. 같은 색인 카드들은 모두 같은 박스에 있어야 한다.(조커 박스는 예외)

이동을 한 박스에서 1장 이상의 카드를 빼서 다른 박스에 넣는 것이라고 정의한다.
이때 빼내는 카드들의 색깔이 같지 않아도 된다.
각각의 박스에 들어있는 카드의 개수가 색을 구별해서 주어질 때 위 조건들을 만족하게 만드는 상태로 만들 수 있는 최소 이동의 횟수를 구해야 한다.

풀이

한 박스를 조커 박스로 정의하고 나머지 N-1개의 박스에 있는 카드들을 모두 조커 박스로 넣어도 위 조건을 만족하기 때문에 나올 수 있는 최대 이동 횟수는 N-1이다.
문제의 조건을 만족하는 상태에서 상자의 상태는 아래 3가지 중 하나이다.

1. 조커 박스
2. 하나의 색상이 들어있는 박스
3. 비어있는 박스

2가지 색의 카드가 들어있든, M가지 색의 카드가 들어있든, 조커 박스가 아닐 경우 이동 횟수를 1 소모하는 것은 똑같기 때문에 상자 내부에 들어있는 카드들의 색의 종류가 2개 이상일 경우 이동 횟수를 소모해 1번이나 2번 상태로 만들어줘야 한다.
상자를 처리할 때 색깔 상자를 먼저 만들고, 색깔 상자가 이미 있고 조커 박스가 비어 있는 경우 조커 박스로 만들어줘야 한다.
조커 박스를 먼저 만들어버리면 아래 TC를 통과하지 못한다.

3 2
1 0
0 1
0 1

• 최적의 해는 0이지만, 조커 박스를 먼저 만들면 (조커, 2번 색 상자, 이동)으로 1이 나오게 된다.

소스코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] input = br.readLine().split(" ");
        int n = Integer.parseInt(input[0]), m = Integer.parseInt(input[1]), jok=-1, moves=0;
        int[] ccnt = new int[n], ckind=new int[n], inuse=new int[m];
        int[][] cinb = new int[n][m];
        for(int i=0;i<m;i++) inuse[i]=0;
        for (int i = 0; i < n; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int c=0, ck=0;
            for (int j = 0; j < m; j++) {
                cinb[i][j] = Integer.parseInt(st.nextToken());
                if(cinb[i][j]!=0){
                    c++;
                    ck=j;
                }
            }
            ccnt[i] = c;
            if(c==1) ckind[i]=ck;
            else ckind[i]=-1;
        }
        for (int i = 0; i < n; i++) {
            if (ccnt[i] == 0) continue;
            if (ccnt[i] == 1 && inuse[ckind[i]] == 0) {
                inuse[ckind[i]] = 1;
            } else if (jok == -1) {
                jok = i;
            } else {
                moves++;
            }
        }
        System.out.println(moves);
    }
}

풀고나서

• 빼낸 카드의 색상이 같지 않아도 된다는 이동 조건을 보지 못해서 시간이 많이 걸렸다.