[C++] 숫자의 표현 : 구현

정답 코드

#include <string>
#include <vector>
#include <iostream>

using namespace std;

int solution(int n) {
    
    int answer = 0;
    int left = 0, right = 0, cnt = 0;

    while (left < n) {
        if (cnt < n) {
            right += 1;
            cnt += right;
        } else {
            if (n == cnt) {
                answer += 1;
                
                cout << "left " << left << endl;
                cout << "right " << right << endl;
                cout << "cnt " << cnt << endl;
                cout << endl;
            }
            left += 1;
            cnt -= left;
        }
    }
    
    return answer;
}
실행 결과: n = 15일 경우
left 0
right 5
cnt 15

left 3
right 6
cnt 15

left 6
right 8
cnt 15

left 14
right 15
cnt 15

분석

1. while문: left가 n보다 작은 한 계속 반복한다.
2. 내부에는 cnt가 n보다 작을 경우, 클 경우, 같을 경우로 나눈다.
3. 먼저, cnt < n인 경우: right 1 추가, cnt는 이전 cnt에 right를 더한다.
4. 다음, cnt = n인 경우: answer에 1 추가
5. 끝으로, cnt > n인 경우: left 1 추가, cnt는 이전 cnt에서 left를 뺀다.

cnt: 현재 시퀀스까지의 합계
left: 현재 시퀀스의 왼쪽 끝
rifht: 현재 시퀀스의 오른쪽 끝

나의 시도

int solution(int n) {
    
    int answer = 0;
    
    // n이 1 또는 2의 경우 항상 1
    if (n <= 2) return 1;
    
    for (int i = 2; i < n; i++) {
        
        // 약수가 1과 자기 자신 뿐인 소수의 경우 항상 2
        if (n%i != 0) {
            return 2;
        }
        
        // 소수가 아닌 경우
        if ((pow(i, 2)!=n)&&(n%i == 0)) {
            return 4;
        }
    }
    // 약수가 거듭제곱 형태로 존재하는 경우의 n (Ex: 4, 9, 16, 25, ..)
    for (int i = 2; i < n; i++) {
        
        if (pow(i, 2)==n) {
            for (int j = 2; j < n; j++) {
                // 거듭제곱 i가 소수이면 1개
                if (!(n%j==0)) {
                    return 1;
                    
                // 거듭제곱 i가 소수가 아니면 3개
                } else if (n%j==0) {
                    return 3;
                }
            }
        } 
        else return 2;
    }
    
    return answer;
}

• 구현을 완성하지 못했고, 나열 후 하나하나 규칙을 찾으려던 전략이 통하지 않았다.
• 시간도 많이 소요되어, 정답 코드를 확인하였다.