뒤집기 II ( 1455 번 )

1455번: 뒤집기 II

 

---

🧠 알고리즘

• 완전 탐색(Brute Force)

 

✔️ 동작 방식

• 오른쪽 아래부터 모든 칸을 하나씩 확인하면서
• 뒷면(1)이 나올 때마다 그 위치까지의 모든 동전을 뒤집는 모든 경우를 그대로 계산

---

 

🧾 코드

import sys

# 뒤집기 함수
def _reverse_coin(i, j):
    global coin
    for idx_1 in range(i + 1):
        for idx_2 in range(j + 1):
            if coin[idx_1][idx_2] == 1:
                coin[idx_1][idx_2] = 0
            else:
                coin[idx_1][idx_2] = 1


def _main(n, m):
    answer = 0
    
    global coin
    coin = [list(map(int, sys.stdin.readline().rstrip())) for _ in range(n)]
    for i in range(n - 1, -1, -1):
        for j in range(m - 1, -1, -1):
            if coin[i][j] == 1: # 뒷면...
                _reverse_coin(i, j)
                answer += 1

    return answer

n, m = map(int, sys.stdin.readline().rstrip().split())
print(_main(n, m))

---

 

⏱️ 시간 복잡도

for i in range(n - 1, -1, -1) : 코인 배열 탐색 ( 이차형 시간 복잡도 )
	for j in range(m - 1, -1, -1)
		_reverse_coin(i, j) : 뒤집기 함수 ( 이차형 시간 복잡도 )
        
해당 알고리즘 시간 복잡도 : 사차형 시간 복잡도 ( O(n ** 4) )