[BOJ] 1439. 뒤집기(Greedy, 탐욕 기초).py

#. Problem

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

* The copyright in this matter is in BOJ

#. Resolution Process

  1. Read and understand problem

  2. Redefine the problem + abstract

  3. Create solution plan (select Algorithm, Data structure)

  4. Prove the plan (check performance time and usage memory)

  5. Carry out the plan

  6. Look back on the plan and find a way to improve it

#. Solve

그리디 알고리즘의 대표적인 문제이다.

뒤집고, 어떤 상태를 바꾸는 등의 해동.

어떤 조건이 있을 때,

똑같은 행동을 두 번 했을 경우 자기 자신으로 돌아오게 되므로,

한번 행동한 것은 다시 하지 않는다.

그리디 문제에서도 규칙을 찾아 풀 수 있는데,

여기서

0 or 1 은 뒤집어서 같은 숫자로 만들 수 있는 최소 행동은 0번, 바뀌는구간 0개

01 or 10 은 1번, 1개

101 or 010 은 1번, 2개

1010 은 2번, 3개

10101은 2번, 4개

101010은 3번, 5개

가 된다.

여기서 규칙을 찾을 수 있는데,

 (구간 개수 + 1) / 2 로 최소 행동을 구할 수 있다.

#. Python Code

1 2 3 4 5 6

S, res = input(), 0 for i in range(1, len(S)):     if S[i] != S[i-1]:         res += 1   print((res+1)//2)

cs