[Level 2] 6. 숫자의 표현

6. 숫자의 표현

Algorithm - Level 2

- 풀이

복잡해보이지만 생각을 단순하게 하면 쉽다.

1. 3, 5, 7, 9 ... 의 숫자들은 1+2, 2+3, 3+4, 4+5 ... 와 같이 표현이 가능하다.

-> 즉 2로 나눴을 때 나머지가 1이면 다음과 같은 표현이 가능하다 (단, 1은 제외)

2. 1+2+3, 2+3+4, 3+4+5 와 같은 표현이나, 1+2+3+4, 1+2+3+4+5와 같은 식을 표현하기 위해 이중 for문을 사용한다.

3. for문의 효율성을 위해 입력 n의 값의 절반까지만 접근한다. ( 이보다 큰 수는 연속되어 표현이 불가능하다.)

#include <string>
#include <vector>
#include <iostream>
using namespace std;
 
int solution(int n) {
    int answer = 1;
 
    if(n!=1)
        answer = n%2==1 ? answer+1 : answer;
 
    int tmp;
    for(int i=1; i<=n/2; i++){
        tmp = 0;
        for(int j=i; j<=n/2; j++){
            tmp+=j;
            if(tmp>n)
                break;
 
            if(tmp==n){
                answer++;
                break;
            }
        }
    }    
    return answer;
}
 
int main(void){
    int n=15;
 
    cout << solution(n) << endl;
}