[삼성 A형 기출문제] - 17406 배열 돌리기 4

실버2는 너무해 ㅠ.ㅠ

https://www.acmicpc.net/problem/17406

17406번: 배열 돌리기 4

 

입력

• map에 배열을 입력받았다.
• 회전 연산의 정보는 따로 벡터에 담았다.
• 벡터에 구조체로 넣어서 하려고 했는데, 3개 이상의 값을 구조체에 넣으면 크기 순으로 따로 정렬을 해야되고 귀찮아서 vector<pair<pair<int, int>,int>>v; 로 때려박았다

구현

구현은 3가지를 중점적으로 생각했다.

1. 연산에 맞게 배열을 회전시키기 --> rotate 함수 사용
2. 연산의 순서를 정하기 --> next_permutation 사용
3. 각 행별로 더하기 --> calc 함수 사용

우선, `rotate` 함수의 구현은 다음과 같다.

• 배열을 움직여야 하므로 backup 배열에 memcpy 해두었다.
• 움직이는 것은 정사각형으로 움직이므로 좌상단, 우상단의 좌표를 저장해두고 그에 맞게 배열을 이동했다.
• 예를들어 5x5 정사각형이 이동해야하면, 가장 바깥쪽의 정사각형 라인이 움직이고 그 안쪽에 있는 3x3 정사각형도 움직여야 한다.
• while loop을 돌며 좌상단과 우하단의 좌표가 같아지면 1x1 정사각형이다.
• 즉, 가장 안쪽에 있는 정사각형에 도달한 것이므로 이동이 끝났음을 의미한다. break로 탈출한다.

연산의 순서를 정하는 것은 next_permutation을 사용했다. next_permutation은 조사하는 배열의 크기가 20정도만 되어도 시간초과의 위험이 있지만 K가 최대 6이므로 시간초과의 위험은 없다.

• 벡터에 입력받은 회전 연산에 대해 순열을 구했다. 이 값을 rotate 함수에 인자값으로 넘겨주어 rotate 함수에서 좌상단, 우하단 좌표 값을 계산할 수 있다.
• next_permutation 은 정렬된 리스트에만 적용할 수 있으므로 벡터를 정렬해주는것이 중요하다. 어차피 순열만 구하면 되기 때문에 크기순으로 정렬이 되든, 역순으로 정렬이 되든 큰 상관이 없다.

마지막으로 각 행별로 더하여 최소값을 찾는 것은 크게 어렵지 않다.

• 연산의 순서에 맞게 rotate 함수가 끝나고 최종적으로 이동이 완료된 배열을 각 행별로 더해가며 최소값을 구하고 그 값을 return 해주면 된다

소스코드