백준 1080
-
BOJ1080 행렬Algorithm/BOJ 2020. 6. 11. 17:31
출처: www.acmicpc.net/problem/1080 분류: Greedy 접근방식 두 형렬에서 한 행렬을 한번에 3x3 만큼씩 뒤집는 연산을 통해 같은 행렬을 만들 수 있는 최소 연산횟수를 구하는 문제입니다. 처음엔 dfs로 무식하게 모든 경우를 다 해봤는데 이럴 경우 엄청난 연산 횟수로 역시 시간초과가 납니다. 그리디 문제인 만큼 그리디하게 풀면 생각보다 쉽게 해결할 수 있습니다. 0,0 부터 시작해서 n-3까지 가면서 해당 지점이 타겟 행렬과 다르다면 뒤집어줍니다. 0,0부터 시작하기 때문에 해당 점에서 뒤집지 않으면 결코 같은 행렬을 만들 수 없습니다. 같다면 그냥 통과하면 되는거고 다를 경우 연산 횟수를 카운트하면서 넘어가주면 됩니다. 이때 몇 가지 경우를 더 생각해줘야 하는데 같은 행렬을 ..