(Python)백준 코딩테스트 연습 - 뒤집기 II(1456)

1. 문제

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

1455번: 뒤집기 II

2. 풀이

import sys
input = sys.stdin.readline
from collections import deque

# n : 동전의 세로 크기
# m : 동전의 가로 크기
n, m = map(int, input().strip().split())
    
# coinList : 동전 리스트
coinList = deque()
# coinList에 리스트 값 추가
for i in range(n):
    coinList.append(deque(map(int, list(input().strip()))))
    
# reverseCnt : 뒤집은 횟수
reverseCnt = 0

# 세로 줄 역순으로 순회
for i in range(n - 1, -1, -1):
    # 가로 줄 역순으로 순회
    for j in range(m - 1, -1, -1):
#         print(coinList[i][j], end="")
        # 해당 인덱스의 코인이 뒷면(1)이라면 [0][0] 인덱스부터 해당 인덱스까지 뒤집기 수행
        if coinList[i][j] == 1:
            reverseCnt += 1
            for p in range(i + 1):
                for q in range(j + 1):
                    if coinList[p][q] == 1:
                        coinList[p][q] = 0
                    else:
                        coinList[p][q] = 1
print(reverseCnt)

3. FeedBack

 - 해당 문제는 그리디 알고리즘을 이용하여 해결하는 문제이다.

 문제 해결을 위해 당장의 코인 리스트 상태에서 먼저 뒤집어야할 것부터 탐색하여 뒤집기를 수행하는 방식으로 그리디 알고리즘을 구현하여 해결하였다.