[Python] 1455번 뒤집기 II

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

1455번: 뒤집기 II

---

 

22/09/23

 

 

전형적인 그리디 문제로, 문제 상황을 잘 시뮬레이션하면 되는 문제이다.

---

 

문제 접근 방식:

 

 

먼저, 문제 상황을 보자.

 

문제는 모든 동전을 뒤집어서 앞면으로 만들고자 하는 것이 목표이고, 그때의 뒤집는 횟수를 최소화하고 싶은 것이 최종적인 목표이다.

 

한 동전을 선택하면, 맨 위의 좌측 동전부터 선택한 동전까지, 그 직사각형에 해당하는 영역만큼의 동전이 모두 뒤집힌다는 사실을 보고, 그리디적인 접근을 하면 좋을 것이라고 생각했다.

 

위에 사실에 따르면, 맨 아래 우측 동전이 만약 뒤집혀져 있다면, 그 동전을 뒤집는 데에 드는 최소 횟수는 1이다.

 

그리고 맨 아래 우측 동전은 항상 제일 먼저 뒤집어야 이득인데, 왜냐하면 그 동전을 뒤집으면 다른 나머지 동전들의 상태가 전부 다 바뀌기 때문이다.

 

우리는 이렇게 다른 나머지 동전들의 상태가 모두 변함으로써 생기는 어쩔 수 없는 중복된 뒤집기, 다시 말해 뒤집었던 동전을 다시 뒤집는 일을 원치 않는다.

 

예를 들자면,

101
011
010

다음과 같이 동전상태가 주어져 있다고 가정해보자.

 

나는 맨 처음에 내키는 대로 그냥 한가운데의 동전을 뒤집는다고 하면, 다음과 같이 변할 것이다.

011
101
010

그리고 맨 아래 가운데 동전을 뒤집는다고 해보자.

101
011
100

그러면, 저기 좌측 상단의 2*2 모양의 부분이 다시 맨 처음 상태와 같아진 것을 확인할 수 있다.

 

어차피 1을 없애려면, 거기에 해당하는 동전을 뒤집거나 다른 동전 뒤집기에 영향을 받아서 뒤집히는 거로만 1을 없앨 수 있다.

 

그 말은 곧, 언젠가 다시 한가운데 동전을 뒤집어야 되는 순간이 올 수도 있다는 말이다.

 

이는 맨 처음에 내가 한가운데 동전을 뒤집는 행위에 손해를 보는 것이다.

 

때문에 나는 여기서 아이디어를 얻어서 우측에서 좌측 순으로, 맨 아래에서 맨 위 순으로 차근차근 뒤집는 것으로 생각했다.

 

왜냐하면 우측 하단은 자기 자신을 선택하여 뒤집는 것 외로는, 다시 말해 다른 동전 뒤집기에 영향을 받아 뒤집히지 않기 때문이다.

 

또한, 우측->좌측, 하단->상단 순으로 다른 동전 뒤집기에 영향을 많이 받기 때문에, 영향을 적게받는 동전 뒤집기를 먼저 수행함으로써 선택했던 동전을 다시 선택하여 뒤집는 일이 최대한 없게 끔 할 수 있기 때문이다.

 

이 아이디어를 가지고 실제로 뒤집는 함수를 구현하고, 그 함수를 우측->좌측, 하단->상단 순으로 뒤집기 함수를 실행함으로써 구현하였다. 

---

아래는 내가 위의 접근 방식과 같이 작성한 파이썬 코드이다. 더보기를 누르면 확인할 수 있다.

# 1455번 뒤집기 II
# 그리디, 구현, 시뮬레이션
import sys
input = sys.stdin.readline

def reverse(i, j):
    for m in range(i+1):
        for n in range(j+1):
            if matrix[m][n]:
                matrix[m][n] = 0
            else:
                matrix[m][n] = 1

N, M = map(int, input().rstrip().split())
matrix = [list(map(int, input().rstrip())) for _ in range(N)]
reverse_time = 0
for i in range(N-1, -1, -1):
    for j in range(M-1, -1, -1):
        if matrix[i][j]:
            reverse(i, j)
            reverse_time += 1

print(reverse_time)