[Level 4] 숫자의 표현

• 안녕하세요. BlockDMask 입니다.

• 오늘은 Level 4의 '숫자의 표현'을 풀어봤습니다.

• 날이 점점 추워지네요.... 일교차도 크고;;감기 조심하세요;;

0. 문제

• Programmers Level 4 숫자의 표현

• Programmers Level 4 expressions

1. 문제설명

• 연속된 자연수 합으로 어떤 숫자를 표현하는 방법이 여러가지 입니다.

• 예를들어 자연수 15는
  1+2+3+4+5 = 15
  4+5+6 = 15
  7+8 = 15
  15 = 15
  로 표현이 가능합니다.

• 숫자를 입력받아 연속된 수로 표현할 수 있는 케이스의 개수를

• 반환하는 expression 함수를 완성하면 됩니다.

• 15가 들어오면 4를 반환하면 됩니다.

2. 풀이과정

• 총 두가지 방법으로 문제를 풀어보았습니다.
  단순하게 생각해서 1)번 으로 풀었는데 시간복잡도가 이렇게 나오고;;
  Level 4 가;; 이렇게 쉬운 문제일 리가 없다고 생각했습니다.
  시간 복잡도를 줄이려고 고민하던 찰나에 2)번과 같은 방법이 생각났습니다.

1) 2중 for 문을 이용한 방법 (시간 복잡도 N^2)

i 값에서 부터 하나씩 더해가면서 TestCase 와 같은지 확인을 합니다.

TestCase 와 같으면 갯수가 하나 증가되고

TestCase 보다 크면 갯수는 그대로 이고.

i 값이 하나 증가됩니다.

이런식으로

TestCase 가 15일때 

1+2+3+4+5 = 15  : answer 증가, for문 하나 나와서 i 증가

2+3+4+5 +6 = 20 > 15  : answer 그대로, for문 하나 나와서 i 증가

.

.

.

.

으로 계산을 합니다.

2) 2중 for 문과 다를 바 없는 1중 while 문을 이용한 방법 (시간 복잡도 N)

위에있는 알고리즘을 반복문 하나로 바꿨습니다.

어짜피 연속된 숫자이므로 

가운데 부분은 두고,

맨앞을 제거하고

맨뒤를 추가하면 되지않냐.

는 생각에서 

결론이 나왔습니다.

3. 코드

1) 이중 반복문 (for 문 두개)

#include<iostream>
using namespace std;
 
int expressions(int testCase) {
    int answer = 0;
 
    int tmp = 0;
    for(int i=0; i<testCase ; i++){
        tmp = i;
 
        for(int j=i+1; j<testCase; j++){
            tmp += j;                       //연속으로 셈 해줍니다.
 
            if(tmp == testCase){            //연속으로 더한 값이 testCase와 같은 경우
                answer++;
            }else if(tmp > testCase){       //연속으로 더한 값이 testCase보다 큰 경우
                break;
            }
        }
 
    }
 
    //마지막에 '자기 자신인 경우'를 더해준다.
    return ++answer;
}
 
int main() {
    int testNo = 35;
    int testAnswer = expressions(testNo);
// 아래는 테스트로 출력해 보기 위한 코드입니다.
    cout<<testAnswer;
}
 

2) 반복문 하나 (while 문 하나)

#include<iostream>
using namespace std;
 
int expressions(int testCase) {
    int answer = 0;
 
    int tmp = 0;
    int low =1, high =2;
 
    tmp = low;
    while(1){
 
        if(tmp == testCase){        //testCase 와 같으면 answer를 하나 추가하고
            answer++;               //맨앞에 작은 숫자를 하나 제거한다.
            tmp -= (low++);
        }else if(tmp > testCase){   //testCase 보다 커지면 맨앞 작은 숫자 하나 제거
            tmp -= (low++);
        }else{                      //testCase 보다 작으면 하나 큰수를 더한다
            tmp += (high++);
        }
 
        if(high == testCase) break;
    }
 
 
    //마지막에 '자기 자신인 경우'를 더해준다.
    return ++answer;
}
 
int main() {
    int testNo = 35;
    int testAnswer = expressions(testNo);
// 아래는 테스트로 출력해 보기 위한 코드입니다.
    cout<<testAnswer;
}
 

4. 인증

문제출처 : https://programmers.co.kr/learn/challenge_codes/156

감사합니다.

도움이 되었다면 하트 한번 부탁드립니다.