연속된 자연수의 합 (백준 2018번 : 수들의 합 5)

https://www.inflearn.com/course/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98/dashboard

it 취업을 위한 알고리즘 문제풀이 (with C/C++) : 코딩테스트 대비 - 인프런 | 강의

인프런 강의 듣다가 .. 뭔가 백준에 유사한 문제 있었던 것 같아서 찾다가 풀어봄. 혼자 풀은거라 강사님 풀이와는 다르니까 ㅋㅋㅋㅋㅋㅋㅋㅋ 블로그에 기록해두려고 급하게 켰다. 

 

백준 2018번 문제

뭔가 규칙성이 있을 것 같아서 좀 고민해보다가 풀었다. 예를 들어 15의 경우 15 (1개의 숫자), 7+8 (2개의 숫자), 4 + 5 + 6 (3개의 숫자), 1 + 2 + 3 + 4 + 5 (5개의 숫자) 이런식으로 표현이 가능하다. 

 

이 규칙성에 대해서 생각해보자

덧셈에 사용되는 숫자 개수	규칙성	n을 덧셈식으로 나타내는 법
2	1 + 2 = 3 2 + 3 = 5 3 + 4 = 7.... 3으로 시작해서 2씩 늘어남	n에서 처음 숫자 3을 빼고 ÷2를 한 몫에 +1, +2 Ex ) (15 - 3) / 2 = 6이므로 7, 8 15 = 7 + 8
3	1 + 2 + 3 = 6 2 + 3 + 4 = 9 3 + 4 + 5 = 12 6으로 시작해서 3씩 늘어남	n에서 처음 숫자 6을 빼고 ÷3을 한 몫에 +1, +2, +3 Ex ) (15 - 6) / 3 = 3이므로 4, 5, 6 15 = 4 + 5 + 6
4	1 + 2 + 3 + 4 = 10 2 + 3 + 4 + 5 = 14 3 + 4 + 5 + 6 = 18 10부터 시작해서 4씩 늘어남	n에서 처음 숫자 10을 빼고 ÷4를 한 몫에 +1, +2, +3, +4 Ex ) (22 - 10) / 4 = 3이므로 4, 5, 6, 7 22 = 4 + 5 + 6 + 7
5	1 + 2 + 3 + 4 + 5 = 15 2 + 3 + 4 + 5 + 6 = 20 3 + 4 + 5 + 6 + 7 = 25 15부터 시작해서 5씩 늘어남	n에서 처음 숫자 15를 빼고 ÷5를 한 몫에 +1, +2, +3, +4, +5 Ex ) (30 - 15) / 5 = 3이므로 4, 5, 6, 7, 8 30 = 4 + 5 + 6 + 7 + 8
6	1 + 2 + 3 + 4 + 5 + 6 = 21 2 + 3 + 4 + 5 + 6 + 7 = 27 3 + 4 + 5 + 6 + 7 + 8 = 33 21부터 시작해서 6씩 늘어남	n에서 처음 숫자 21을 빼고 ÷6를 한 몫에 +1, +2, +3, +4, +5, +6 Ex ) (39 - 21) / 6 = 3이므로 4, 5, 6, 7, 8, 9 39 = 4 + 5 + 6 + 7 + 8 + 9

표를 보면 알 수 있듯, 2개의 연속된 숫자로 만들 수 있는 가장 작은 숫자는 3이고, 2간격으로 늘어난다. 이 규칙성을 찾은 다음 덧셈식에 규칙을 적용해보면 위의 표 가장 오른쪽처럼 적용할 수 있다. 

 

이를 코드로 구현하기 위해 일반화를 시켜보면, 아래 표와 같다.

이 때 덧셈에 사용되는 숫자의 개수별 초기값은 3, 6, 10, 15... 이런 식으로 늘어난다. (더하는 수가 1씩 증가하는 규칙이 있다. +3, +4, +5...) 그래서 코드 상에서는 standard = standard + i로 계속 갱신해주면 된다. 

덧셈에 사용되는 숫자 개수	덧셈식으로 나타내기
i	입력받은 숫자 n에서 초기값 standard빼고 i로 나눈다. (ex. (15 - 3) / 2) 이 몫에 +1, +2, ... +i가 될때까지 더한다. (6 + 1, 6 + 2)

 

---

 

우선 아래 코드는 인프런 강의 문제를 스스로 풀어본 코드이다. 백준과 다른 점이라면, 자기 자신으로만 이루어진 것은 카운트 하지 않고, 가능한 수식을 다 출력해줘야한다. (그래서 반복문이 중첩되어 있다. )

int main() {
    int i, j, num, temp, count = 0, standard = 1;
    scanf("%d", &num); //배분할 숫자 입력받음
    temp = num; //직접 num을 조작하지 않기 위해 temp에 값 복사

    for(i=2; temp-standard > 0; i++) {
        standard += i;
        if((temp-standard) % i == 0) {
            for(j=1; j<i; j++) { //i개의 숫자의 합으로 표현하기 위해 j=i만큼 출력용 반복문 돌림.
                printf("%d + ", (temp-standard)/i+j);
            }
            printf("%d = %d\n", (temp-standard)/i+j, num);
    		count++;
        }
    }
    printf("%d\n", count);
}

변수 설명

- i : 덧셈에 사용되는 숫자 개수,

- j : +1, +2, ... +i까지 몫에다가 더하는 용. 그런데 수식을 만들어야하므로 j <=i가 아니고 j< i까지 한다음, 마지막 출력문은 빼주었다. 

- count : 수식 개수

 

코드 설명 

for(i=2; temp-standard > 0; i++) {
	standard += i;

-> standard가 초기값이므로 temp가 standard보다 진행 중지. 위에서 설명했듯 i는 덧셈식을 이루는 숫자 개수

-> standard += i는 각 숫자 개수 별로 초기값 갱신을 위한 코드

if((temp-standard) % i == 0) {

-> 15에서 3빼고 2로 나눴을때 나누어떨어진다 == 15를 2개의 숫자의 합으로 표현가능하다 

-> 합으로 표현 가능한경우만 수식 출력하면 되므로

for(j=1; j<i; j++) { 
	printf("%d + ", (temp-standard)/i+j);
}
printf("%d = %d\n", (temp-standard)/i+j, num);
count++;

-> i만큼 몫으로 나온 숫자인 (temp - standard) / i에 각각 더해주면 된다. 

-> j가 1부터 시작해서 1, 2, 3, ... i까지 더해줘야한다. 수식형태를 만들어야 해서 마지막 더하는 숫자는 반복문 밖으로 뺐다. 

-> count를 증가시킨다. 

 

---

백준 코드 

#include <stdio.h>

int main() {
    int i, j, num, temp, count = 1, standard = 1;
    scanf("%d", &num);
    temp = num;

    for(i=2; temp-standard > 0; i++) {
        standard += i;
        if((temp-standard) % i == 0) {
    		count++;
        }
    }
    printf("%d\n", count);
}

위 코드보다 많이 단순화 되었다. count만 출력하면 되기 때문... 

대신 백준은 자기 자신만으로 표현하는것도 들어가서 count를 처음에 1로 초기화시켜놨다. (어떤 수든 자기 자신이 포함되니까) 그리고 수식 출력하는 부분만 다 날리면 된다. 

채점 결과는 이렇게 나왔다. 기억에서 날아가기 전에 블로그에 쓴다...