[Java] 백준 13021 공 색칠하기

문제

공 N개가 한 줄로 놓여져 있다. 공은 검정색 또는 흰색으로 칠할 수 있으며, 처음에 모든 공의 색은 흰색이다. 공은 가장 왼쪽이 1번이고, 순서대로 번호가 매겨져 있다.

오늘은 공을 칠해보려고 한다. 공은 기계를 이용해서 칠할 수 있는데, 기계는 두 정수 L과 R을 입력으로 받는다. 기계는 L번째 공부터 R번째 공까지를 흰색이나 검정색으로 모두 칠한다.

기계를 총 M번 사용했고, 이때 입력한 L과 R을 모두 알고있다. 하지만, 어떤 색으로 칠했는지는 까먹고 말았다. 

기계를 모두 M번 사용했을 때, 나올 수 있는 색 조합의 경우의 수를 구하는 프로그램을 작성하시오.

 

입력

첫째 줄에 공의 개수 N과 기계를 사용한 횟수 M이 주어진다. (1 ≤ N ≤ 1,000, 1 ≤ M ≤ 50)

둘째 줄부터 M개의 줄에는 기계를 사용할 때 입력한 L과 R이 기계를 사용한 순서대로 주어진다. (1 ≤ L ≤ R ≤ N)

 

출력

첫째 줄에 나올 수 있는 색 조합의 수를 출력한다. 정답은 263-1보다 작거나 같다.

 

문제 링크 :  공 색칠하기

---

설명

문제는 간단하다.

주어진 n개의 공 중에서 m번동안 l과 r사이의 공을 색칠하여 마지막에 나올 수 있는 경우의 수를 구해주면 된다.

 

처음에 아이디어를 구상할 때 l과 r사이의 공들의 횟수를 체크하여 2씩 곱하면 될까 하는 생각을 했다.

그건 불가능한 방법이였고, 두번째로 생각한 방법이 각 m번째마다 해당되는 공의 수를 올려주는 것은 어떨까 생각했다.

정답과 거의 비슷한 아이디어였지만 그걸로 어떻게 같은 횟수로 칠해진 공인지 구분하는 방법이 떠오르지 않아 그냥 다른 사람 코드를 참고했다.

 

공은 하얀색과 검정색 두가지 경우의 수가 있고 한번에 같이 칠해진 공들을 구분해주어야 한다.

 

위 그림은 공이 4개 기계가 움직인 횟수가 2번인 상황이다.

처음에 1번에서 2번까지 색을 입히고, 두번째에서 2번에서 3번까지 색을 입혔다.

 

공에 숫자가 의미하는 바는 1번째에 칠해진 공. 이라는 의미이다.

 

이 숫자로 총 경우의 수를 구할 수 있는데 일단 같은 숫자의 공은 같은 횟수에 칠해졌다는 의미이므로 하나의 경우의 수로 체크한다. (기계가 한번에 하나의 색밖에 칠하지 못하므로)

 

그리고 한번이라도 칠해진 공은 2가지의 경우의 수(흰, 검)가 생기므로 경우의 수를 체크해준다.

 

하나의 경우의 수당 흰색과 검정색의 경우의 수가 있으므로 2^전체 경우의 수 를 해준다.

 

문제도 잘 봐야하지만 내가 작성한 코드도 잘 보도록 하자.

ans 변수를 long으로 잡고 출력부분에서 (int) 로 해서 계속 맞왜틀을 외쳤다...ㅠ

코드

import java.util.*;
import java.io.*;
import java.util.regex.Pattern;

public class Main {
    public static void main(String[] args) throws Exception {
        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[] arr = new int[n];
        while (m --> 0){
            st =new StringTokenizer(br.readLine());
            int s = Integer.parseInt(st.nextToken());
            int e = Integer.parseInt(st.nextToken());
            for (int i= s -1; i < e; i++){ // 시작 공부터 끝 공까지 순서 기록
                arr[i] = m +1;
            }
        }
        long ans = 0; boolean[] visit = new boolean[51];
        for (int i = 0; i < n; i++){
            if (!visit[arr[i]] && arr[i] != 0){ // 해당 순서를 들리지 않았으면서 0이 아닌경우
                ans++;
                visit[arr[i]] = true;
            }
        }
        System.out.println((long) Math.pow(2, ans));
    }
}