[백준] 2561번 세 번 뒤집기

PS/BOJ

ekwoo 2019. 2. 25. 08:59

문제요약 : 수열의 구간 (xi,yi)를 순차적으로 뒤집어 원래 수열로 만들 때, xi,yi(i=1~3) 를 출력하라

조건 :

1. 정수 N (5≤N≤1000)

2. 구간[i,i]를 뒤집으면 아무런 변화가 없는데 이러한 것도 허용이 된다.

해설 :

주어진 수열의 부분수열을 뒤집는 행위를 세 번 반복하여 1, 2, ... ,N이 되는 수열로 만드는 문제다.

조건 2를 보면 굳이 세 번 뒤집을 필요가 없음을 알 수 있다.

즉, 두 번 뒤집고 1,1을 뒤집거다 한 번 뒤집고 1,1을 두번 뒤집으면 되는 것이다.

우선 처음 수열이 1씩 증가하는 수열이기때문에 이 수열을 세 번 뒤집으면

1씩 증가하거나 1씩 감소하는 부분이 k개 생긴다.

예제에서 6 7 8 2 1 9 3 4 5 10 인데

6 7 8 | 2 1 | 9 | 3 4 5 | 10 이렇게 나눌 수 있다는 것이다.

이때 k는 7보다 작거나 같다 (세 번 뒤집었으니까!)

즉 구간이 최대 7개 나온다는 것은

(7C2)^3만에 모든 구간을 다 뒤집어 볼 수 있다는 말이 된다.

=> 백트래킹으로 답을 구해보도록 하자

※

데이터를 추가해서 확인해보자.

백트래킹으로 답이 안나오는 경우인데, 이는 구간을 잘못 나눠줘서 그렇다.

정 귀찮으면 한 번 뒤집어놓고 백트래킹 돌리는 것도 한가지 방법이고,

1개짜리 구간을 따로 설정해두어 보는 것도 한가지 방법이 될 듯 하다.