7510. 상원이의 연속 합 - D3

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWoEzJFa2A4DFARq

SW Expert Academy

최근 SW Expert Academy의 문제를 난이도 순으로 전부 다 풀어보고 있는 중입니다.

 

현재까지는 난이도 낮은 문제들만 풀어서 따로 리뷰를 적을 일이 없을 줄 알았는데, 이 문제는 한 번 다루어보고 넘어가는 것이 좋은거 같아서 들고 왔습니다.

---

이 문제는 연속된 자연수의 합으로 원하는 값을 찾고 그 갯수가 몇 개인지를 파악하는 문제입니다.

 

솔직히 N의 범위가 10^6이라는 낮지 않은 범위였지만, D3라는 낮은 난이도에 정답률이 높아, 생각하기 귀찮아서 두 번의 반복문으로 풀어보니 시간이 1,454ms 떴습니다.

#include <stdio.h>
 
int main(void) {
    int T;
    scanf("%d", &T);
    for (int t = 1; t <= T; t++) {
        // 입력
        int N;
        scanf("%d", &N);
         
        // 풀이
        int result = 0;
        for (int i = 1; i <= N; i++) {
            int num = 0;
            for (int j = i; j <= N; j++) {
                num += j;
                if (num == N) result++;
                else if (num > N) break;
            }
        }
        printf("#%d %d\n", t, result);
    }
}

보통 이 정도 시간이면 다른 곳들은 오답처리가 될텐데, 낮은 난이도라서 Pass가 뜬거 같습니다.

 

그래서 시간을 한 번 줄여보고자 다른 풀이를 한 번 제출해보았습니다. DP적인 느낌으로 (정확한 DP는 아닙니다, DP 잘 몰라요 ㅎㅎ..) for문을 한 번 돌리되 그 수가 커지면, 앞에서 부터 기록한 값들을 하나씩 제거해가는 방법을 사용했습니다.

 

그러니 약 앞서 나온 시간의 약 1/4의 값으로 줄일 수 있었습니다. 321ms

#include <stdio.h>
 
int main(void) {
    int T;
    scanf("%d", &T);
    for (int t = 1; t <= T; t++) {
        // 입력
        int N;
        scanf("%d", &N);
         
        // 풀이
        int result = 0;
        int num = 0;
        int temp = 1;
        for (int i = 1; i <= N; i++) {
            num += i;
            while (num > N) {
                num -= temp;
                temp++;
            }
            if (num == N) result++;
        }
        printf("#%d %d\n", t, result);
    }
}

그런데 정답 코드들 중 6ms라는 괴랄한 시간의 값이 눈에 들어왔습니다. 보통 이 정도 시간이라면 10^6을 한 번의 순회로 정답을 도출한 것인데, 저는 도저히 그 방법을 떠올리지 못했습니다.

 

그래서 알아보니 제가 너무 컴퓨터 연산 능력에 의존한 나머지 제 머리를 굴리지 않아, 이 문제를 수학적으로 다가갈 생각을 안했었던 것이었습니다.

 

결국 이 문제는 $$N = x + (x + 1) + (x + 2) + ... + (x + y)$$를 해결하면 되는 문제입니다.

 

여기서 N은 주어지는 숫자이며, x는 이어지는 자연수의 시작 위치, y는 연속된 숫자의 갯수가 되겠죠. 이 수식을 풀어내면 아래와 같은 결과값을 가질 수 있습니다.

$$ x = (N - y * (y + 1) / 2))/(y + 1)$$

그렇다면, 어떻게 이를 이용해 정답을 구할 수 있을까요? 방법은 간단합니다. N의 경우엔 문제에서 주어지는 답이며, 문제는 x와 y인데, 저희는 y를 반복문으로 순회하며 임의로 정하고 이로 인해 만들어진 x가 정수인지 아닌지만 파악을 하면 됩니다.

 

단, 분자에 들어가는 $$(N - y*(y+1)/2)$$가 0보다 커야합니다. x는 자연수니까요. 그렇다면 y를 순회할 때 범위를 어느 정도로 잡아야 하냐가 분자에 의해 결정이 되겠죠.

 

이렇게 문제를 해결한다면 6ms의 시간을 가진 풀이를 만들 수 있습니다.

#include <stdio.h>
 
int main(void) {
    int T;
    scanf("%d", &T);
    for (int t = 1; t <= T; t++) {
        // 입력
        int N;
        scanf("%d", &N);
 
        // 풀이
        int result = 1; // 자기자신을 포함하고 있습니다.
        for (int y = 1; y <= N; y++) {
            int chil = (N - y * (y + 1) / 2);
            int pare = (y + 1);
 
            if (chil <= 0) break;
            result += (chil % pare == 0);
        }
        printf("#%d %d\n", t, result);
    }
}

이번 문제는 계산을 컴퓨터에만 의존하려 했던 저에게 일침을 날린 문제인거 같습니다. 깨달은 점이 많네요. 앞으로는 컴퓨터보다 제 머리를 굴려서 문제를 풀어봐야겠습니다.

---

이상 7510. 상원이의 연속 합 - D3였습니다. ^_^