[백준 20365번] 2xn 타일링

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

20365번: 블로그2

 

접근 과정
1. 어떤 문제로 이해 했는가? 그리고 문제의 제약 조건은?

연속된 임의의 문제들을 선택하고 선택된 문제들을 전부 원하는 같은 색으로 칠하는 작업을 한다.
해결한 경우 파란색, 해결하지 못한 경우 빨간색으로 칠한다.
가장 효율적인 방법으로 위 작업을 수행하기를 원한다. 각 문제를 주어진 색으로 칠할 때 필요한 최소한의 작업 횟수를 구하는 프로그램을 작성하라.

 

시간제한 : 2초

문제의 수 N (1 ≤ N ≤ 500,000)

2. 나의 방식대로 문제를 재정의 하자.

파란색, 빨간색의 덩어리가 몇개인지 수를 세고, 더 많이 칠한 색을 한번에 칠하고,

적게 칠한 색을 하나씩 칠하는 것이 가장 적은 작업횟수를 가진다.

 

 

3. 어떤 알고리즘과 자료구조를 사용할 것인가?

int형 temp로 파란색, 빨간색의 분기를 구분하게 하고 각 덩어리의 수를 센다.

 

 

4. 어떻게 계산할 것인가?

1) 입력

BufferedReader

 

2) 시간 복잡도 계산

O(n)

 

 

5. 주의할 점은 무엇인가?

 

 

 

6. 풀이 과정

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

public class q20365 {

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

    Integer N = Integer.parseInt(br.readLine());
    String str = br.readLine();

    Character color = str.charAt(0);
    Integer[] colorCount = new Integer[2];
    Integer temp = 0;

    colorCount[0] = 1;
    colorCount[1] = 0;

    for (int i = 1; i < str.length(); i++) {

      if (str.charAt(i) == color) {
      } else {
        temp = (temp == 1) ? 0 : 1;
        colorCount[temp] += 1;
        color = str.charAt(i);
      }
    }
    
    System.out.println(Math.min(colorCount[0], colorCount[1]) + 1);
    br.close();
  }

}

 

 

7. 개선점