Codeforces Round #642 (Div. 3) [못푼 문제]

처음에 치렀던 코드포스 Div3 문제들을 시간 내에 못 푼 문제 들을 다시 한번 풀어 보았다.

물론 진짜 못 풀 겠는 문제들은 구글링을 통하여 해법을 어느정도 제시받았다.

처음이었던 만큼 (핑계이기도 하지만)  모든 면에서 미숙하게 문제를 접근하고 풀었던 것 같다.

문제들은 뒤로 갈수록 어려워진다는 것은 알고 있어서 최대한 1-3번 문제들을 위주로 풀어 보려고 했었던 것 같다.  

 

 

[C. Board Moves]

 

이 문제는 다시 풀어보니 조금 쉬운 Dp 문제였다

내가 대회 도중 이 문제에 대해서 접근했을 때는 예제 입력 조차 이해가 안 되었고 막상 생각 하기를 단순한 수학 문제나 

분할 정복 문제일 것이라고 생각을 했지만 이는 아니었다.

예제 입력 조차 이해를 못 한 것에는 내가 영어 지문을 해석을 제대로 해석을 못한 이유도 있고

한 가지 풀이에만 너무 사로 잡혀 있어서 다른 방향으로 생각을 시도 하지 못 했던 것이 가장 크다.

 

이 문제는 N * N 배열이 있을 때 각 각의 원소들을 한 곳으로 모으는데 필요한 최소 횟수(?)를 구하는 문제이다.

각 각의 칸에서는 모서리 혹은 꼭짓점을 공유하는 인접한 칸으로 이동할 수 있다

예를 들어 밑에 사진과 같이 8개의 방향으로 이동 가능하다.

당연히 보드의 밖으로는 이동 불가능하다.

 

내가 이 문제에 대해 처음으로 생각했던 잘못된 방식으로는 한 칸에 여러의  figures들이 있을 경우

한 번의 이동으로 figures 들을 이동시킬 수 있을 거야 라는 생각을 가지고 문제를 풀려했기에

예제 입력 조차 이해를 못하고 못 풀었던 것 같다 ㅠㅠ

 

빠르게 문제를 이해해 보자.

 

N = 1 인 경우

그 자체로 한 곳에 모여 있다고 볼 수 있기 때문에 필요로 하는 정답은 0 이 된다.

 

N = 3 인 경우

이 숫자들을 어디로 모이게 해야 최소가 될 것인가를 우선적으로 생각해보자. 

표에 표시를 해놨듯이 가운데로 모이게 해야 최소가 될 것이다

그 이유는 다음 표를 보면 이해할 수 있을 것이다.

왼쪽 표는 한쪽으로 모으는데 8번 만에 한쪽으로 모을 수 있고

반면 오른쪽 표는 13번 만에 한쪽으로 모을 수 있을 것이다.

이는 당연하게 각각의 칸에 모두가 가까워야 최소 이기 때문에

오른쪽과 같이 한쪽으로 치우쳐진 곳으로 모으는 것보다 최소 일 것이다.

이를 이용하여 문제를 풀어 보자!

 

N = 5 인 경우를 예를 들어보자

 

N = 5인 경우는 N = 3인 경우의 최소 횟수와 아무것도 칠 해져 있지 않은 칸 들을  가장 가운데 인

진한 파란 칸으로 모으는 횟수의 합으로 볼 수 있지 않을까? 

위에 그림에서 보았듯이 한 곳으로 모이기 위해서는 가장 가운데로 모아야 한다!!

하지만 우리는 Dp[3] 을 알고 가장자리 칸들을 가장 가운데로 모으기 위한 연산 횟수를 더해 주면 된다.

그리고 아무것도 칠 해져 있지 않은 즉 가장자리 칸들은

모두 동일하게 모서리에서 가운데로 가는 횟수와 모두 동일한 것을 알 수 있다.

 

점화식을 정의해 보면 

Dp[i] = Dp[i-2] + (i*i - (i-2)*(i-2)) * diag 이 될 것이다. 

바로 소스 코드를 들여다보자

 

 

[소스 코드]

#include <iostream>
using namespace std;
typedef  long long ll;
const int MAX = 500000 + 1;
int n, t;
ll dp[MAX];
int main() {
    dp[1] = 0;
    for (int  i = 3, diagnol = 1; i < MAX; i += 2, diagnol++) {
        dp[i] = dp[i - 2] + (ll)((i * i) - ((i - 2) * (i - 2))) * diagnol;
    }
    cin >> t;
    while (t--) {
        cin >> n;
        cout << dp[n] << '\n';
    }
    return 0;
}