[프로그래머스/C++] 숫자의 표현

미숙한 블로그 주인이 코딩테스트 문제를 풀어가는 과정을 담은 글입니다. 이 풀이가 효율적인 풀이가 아닐 수 있으며, 부정확한 정보가 많이 있을 수 있습니다. 보완해야할 점이 있다면 댓글로 남겨주세요!

 

https://programmers.co.kr/learn/courses/30/lessons/12924

코딩테스트 연습 - 숫자의 표현

숫자의 표현

문제

Finn은 요즘 수학공부에 빠져 있습니다. 수학 공부를 하던 Finn은 자연수 n을 연속한 자연수들로 표현 하는 방법이 여러개라는 사실을 알게 되었습니다. 예를들어 15는 다음과 같이 4가지로 표현 할 수 있습니다.

• 1 + 2 + 3 + 4 + 5 = 15
• 4 + 5 + 6 = 15
• 7 + 8 = 15
• 15 = 15

자연수 n이 매개변수로 주어질 때, 연속된 자연수들로 n을 표현하는 방법의 수를 return하는 solution를 완성해주세요.

제한사항

• n은 10,000 이하의 자연수 입니다.

 

풀이

입출력 예시

 

풀이

한 가지 확실한 점은, n / 2 한 수의 1을 더한 값 보다 큰 수를 더하면 무조건 n보다 커진다는 점이다.

ex) 15 / 2 + 1 = 8, 8 + 9 = 17

 

이점을 이용해서 n / 2 + 1부터 시작해서 연속되는 수가 나오면 answer을 1씩 증가시켜줬다.

 

1. a에서부터 연속된 자연수들의 합이 n과 같으면 answer++하고 a--

2. 아니라면 a--

#include <string>
#include <vector>

using namespace std;

int solution(int n) {
    int answer = 1; // 자기 자신
    int a = n / 2 + 1;
    int num = 0;
    
    while (a > 0) {
        num = 0;
        for (int i = a; i > 0; i--) {
            num += i;
            if (num == n) {
                answer++;
                a--;
                break;
            }
            else if (num > n) {
                a--;
                break;
            }
        }
        if (num < n) {
            a--;
        }
    }
    
    return answer;
}

 

그런데, 이렇게만 하니까 15번이랑 18번 케이스에서 막혔다.

 

원인은 간단했다. n이 1과 2라는 것에 대한 처리가 되어있지 않아서였다. return 1로 지정해서 실행시켜보니 15번과 18번만 통과한 것이 보였다.

뭐가 1이고 2일지는 모르겠지만, 확실한 것은 1과 2에대한 처리를 해주면 해결 될 문제였다.

#include <string>
#include <vector>

using namespace std;

int solution(int n) {
    int answer = 1; // 자기 자신
    int a = n / 2 + 1;
    int num = 0;
    
    if (n < 3) { // 1 or 2
        return 1;
    }
    
    while (a > 0) {
        num = 0;
        for (int i = a; i > 0; i--) {
            num += i;
            if (num == n) {
                answer++;
                a--;
                break;
            }
            else if (num > n) {
                a--;
                break;
            }
        }
        if (num < n) {
            a--;
        }
    }
    
    return answer;
}

 

결과