[알고리즘C++]숫자의 표현

오늘의 문제

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

숫자의 표현

나의 풀이

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

using namespace std;

int solution(int n) {
    int answer = 1;
    vector<int>pre;
    pre.push_back(0);
    for(int i=1;i<=n/2+1;i++){
        pre.push_back(pre[i-1]+i);
    }
    for(int i=0;i<=n/2+1;i++){
        for(int j=i+1;j<=n/2+1;j++){
            if(pre[j] - pre[i] > n) break;
            if(pre[j] - pre[i] == n) answer++;
        }
    }
    return answer;
}

모범 답안

#include<iostream>
#include<cmath>
using namespace std;
int expressions(int testCase)
{
    int answer=0;
  int to=ceil((-1+sqrt(1+8*testCase))/2);
    for(int i=1;i<=to;i++)
  {
    if(i%2==1&&testCase%i==0)
    {
      answer++; 
    }
    else if(i%2==0&&(testCase%i)==(i/2))
    {
      answer++;
    }
  }

    return answer;
}

int main()
{
    int testNo = 15;
    int testAnswer = expressions(testNo);
// 아래는 테스트로 출력해 보기 위한 코드입니다.
    cout<<testAnswer;
}

배울 점

• 생각보다 오래걸렸다. 이런곳에서 오래걸리면 안된다!!
• 실행시간을 줄이는 부분에서 조금 시간이 들었다. prefix까지 도입했는데도 안되어 계산을 멈추는 부분을 넣으니 통과했다