취미로 코딩하기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 22683번 문제인 Square Route 이다.
문제는 아래 링크를 확인하자.

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

네 도로로 둘러싸인 사각형이 정사각형을 이룬다는 것과 두 x축과 평행한 도로 사이의 거리 및 두 y축과 평행한 도로 사이의 거리가 서로 같다는 것은 필요충분조건임을 확인하자.

따라서 가능한 모든 x축과 평행한 도로 사이의 쌍에 대하여 가능한 거리별로 몇 개의 도로 쌍이 있는지를 먼저 구한 다음, 가능한 모든 y축과 평행한 도로 사이의 쌍에 대하여 두 도로 사이의 거리와 같은 거리를 갖는 x축과 평행한 도로 사이의 쌍의 개수를 더해나가 문제를 해결할 수 있다.

아래는 제출한 소스코드이다.

#include <iostream>
#include <cstring>
using namespace std;
typedef long long ll;

int N, M;
int A[1500], B[1500];
int cnt[1500001];
ll ans;

void solve() {
    memset(cnt, 0, sizeof(cnt));
    ans = 0;
    for (int i = 0; i < N; i++) cin >> A[i];
    for (int i = 0; i < N; i++) {
        int psum = 0;
        for (int j = i; j < N; j++) {
            psum += A[j];
            cnt[psum]++;
        }
    }
    for (int i = 0; i < M; i++) cin >> B[i];
    for (int i = 0; i < M; i++) {
        int psum = 0;
        for (int j = i; j < M; j++) {
            psum += B[j];
            ans += cnt[psum];
        }
    }
    cout << ans << '\n';
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> N >> M;
    while (N) {
        solve();
        cin >> N >> M;
    }
}