프로그래머스 | 숫자의 표현

 

아이디어를 러프하게 정리하고 시작해보자.

1부터 시작해서 ++해가면서 찾아본다고 했을 때

문제에서 나온 15 같은 경우

1 + 2 + 3 + 4 + 5 (15 성공 ans ++)	2 + 3 + 4 + 5 + 6 (15보다 커짐 pass)
3 + 4 + 5 + 6 (15보다 커짐 pass)	4 + 5 + 6  (15 성공 ans ++)
5 + 6 + 7 (15보다 커짐 pass)	6 + 7 + 8 (15보다 커짐 pass)
7 + 8 (15 성공 ans ++)	15 (15 성공 ans ++)

 

이렇게 총 4가지!

이렇게 하게 되면 총 15/2 = 7 이니까 7번 실행하기 됨.

이러면 n 이 10,000이하의 자연수라고 했을 때 시간을 너무 많이 잡아먹는다는 단점이 있음.

그럼 이것도 dp를 활용해서 풀어볼 수 있지 않을까?

 

싹다 더하는 방식으로 vector를 만든다음에

0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
0	1	3	6	10	15	21	28	36	45	55	66	78	91	105	120

 

약간 투포인터 넉낌으로다가 시도해보자

 

end - st < n 일 경우 수가 더 커져야되니까  end++;

end - st > n 일 경우 수가 더 작아져야되니까 st++;

end - st == n 이면 둘다 ++

 

이런 넉낌

#include <algorithm>
#include <vector>
using namespace std;

int solution(int n) {
    int size = (n+1)/2 + 1;
    
    vector<int>v(size, 0);
    
    for(int i = 1; i<v.size();++i) v[i] = v[i-1]+i;
    
    int ans = 1, st=0, end =1;
    
    while(st<end && end <= size && n>2){ 
    /* n>2를 한 이유는 2일경우 1과2는 연속된 자연수로 n표현이 불가능한데 
    int size = (n+1)/2 + 1; 로 해놔서 vector 크기가 무조건 2 이상으로 설정되기 때문
    그레서 이 조건 안넣고 그냥 돌리면 while 문을 실행하면서 ans++이 한번 실행되고,
    ans가 2개가 되어서 답이 틀리게 나옴*/
    
        if(v[end]-v[st] == n){
            ans++; st++; end++;
        } 
        else {(v[end]-v[st])> n? st++ : end++;}
    }
    
    return ans;
}

 

 

n>2조건 안넣어서 테스트케이스 하나 틀렸었는데 저 조건 넣으니까 통과했다!

성공★