New Year Chaos

생각했던 것

문제에 주어진 배열을 그 상태로 분석하여 각 숫자의 위치에 따라 count 값을 조절하려고 시도했었다.
그러다 보니 두가지 생각이 나왔다.

1. 원래 위치보다 앞에 있는 수 기준 : 앞으로 나온 숫자만큼 더해주고 그 수만큼 뒷자리의 수의 위치변화를 무시한다.
2. 원래 위치보다 뒤에 있는 수 기준 : 원래 위치보다 앞에 있는 수들의 위치변화를 무시하고 뒤로 나온 숫자만큼 더해준다.

둘 다 시도했으나 실패했다. 그 이유는 “뒤로 간 숫자들끼리도 위치를 바꿀 수 있는 경우”를 생각하지 못했기 때문이다. 예를 들어 1 2 5 4 3이라는 배열이 주어졌다면 5가 앞으로 2번 나온 것도 더해줘야 하지만 뒤에서 서로 자리를 바꾼 3, 4도 생각해줘야한다. 앞선 두 방법은 이 경우를 고려하지 못한다.

풀이

결국 힌트를 보고 이해를 했다. 어떻게 보면 당연할 수 있는 생각인데, 주어진 배열을 원래의 오름차순 배열로 바꾸는 횟수를 측정하는 것이다. 2칸까지 밖에 가지 못하고, 왼쪽으로 밖에 가지 못한다는 전제 조건이 있기 때문에 배열의 오른쪽에서부터 출발하면 된다는 것도 발상의 전환이었다. 어찌보면 쉬운 생각이었는데 나는 주어진 예제에서만 너무 머물렀던 것 같다. 좀 더 유연한 사고력이 필요한 부분이다.