개발 블로그

https://www.acmicpc.net/problem/2138 2138번: 전구와 스위치 N개의 스위치와 N개의 전구가 있다. 각각의 전구는 켜져 있는 상태와 꺼져 있는 상태 중 하나의 상태를 가진다. i(1 < i < N)번 스위치를 누르면 i-1, i, i+1의 세 개의 전구의 상태가 바뀐다. 즉, 꺼져 www.acmicpc.net 이 문제는 0번 스위치를 누를지 말지 결정하고 풀어야 하는 문제입니다. 왜냐하면 모든 스위치를 한 번씩 눌러보는 브루트 포스로는 복잡도 문제로 해결할 수 없습니다. 0번 스위치를 누른다면, 1번 스위치만 신경 쓰면 되고, 1번 스위치가 눌러지면 2번 스위치만 고려하면 되기 때문입니다. 그래서 시간 복잡도 O(N)으로 풀 수 있게 됩니다. #include #include..

https://www.acmicpc.net/problem/1080 1080번: 행렬 첫째 줄에 행렬의 크기 N M이 주어진다. N과 M은 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 행렬 A가 주어지고, 그 다음줄부터 N개의 줄에는 행렬 B가 주어진다. www.acmicpc.net 이 문제는 3*3 행렬을 반대로 (0->1, 1->0) 뒤집어서 주어진 A에서 행렬 B로 만들 수 있는 최소 연산 횟수를 물어보는 문제입니다. 이 문제의 핵심은 (N-2) * (M-2)의 연산을 수행해 보는 것입니다. 왜냐하면 이 연산을 모두 수행했을 때, 주어진 행렬 B와 일치하지 않으면 더 이상 행렬 B를 만들 수 없기 때문입니다. 이러한 연산으로 인해, 어떠한 원소를 두 번 뒤집는 것은 원래대로 돌아오기 ..