[백준] 3085번 - 사탕게임
인접한 두 위치의 사탕을 바꾸어 최대한 긴 연속된 같은 종류의 사탕을 만드는 문제이다.
가장 쉬운 방법은 가능한 모든 경우를 다 해보는 것이다. 인접한 좌우 사탕의 위치를 바꾸는 경우의 수는 n(n-1) 이고, 상하 또한 마찬가지다. 즉, 완전 탐색을 사용할 시 시간복잡도는 $O(n^2)$이다.
n이 최대 50이므로 $O(n^2)$이지만 시간초과는 발생하지 않는다.
1 |
|
Programming Diary
인접한 두 위치의 사탕을 바꾸어 최대한 긴 연속된 같은 종류의 사탕을 만드는 문제이다.
가장 쉬운 방법은 가능한 모든 경우를 다 해보는 것이다. 인접한 좌우 사탕의 위치를 바꾸는 경우의 수는 n(n-1) 이고, 상하 또한 마찬가지다. 즉, 완전 탐색을 사용할 시 시간복잡도는 $O(n^2)$이다.
n이 최대 50이므로 $O(n^2)$이지만 시간초과는 발생하지 않는다.
1 |
|