.gif)
study
숫자의 표현[프로그래머스]
Date: 2026-01-20 07:56
Update: 2026-01-20 08:04
[프로그래머스] 숫자의 표현
접근:
- 이중 반복문을 통해 연속된 숫자를 더하면서 매번 체크
- 숫자와 크거나 같다면 break문을 통해 내부 반복문 탈출
- 정해진 숫자와 같다면 일치 하는 숫자 증가
#include <string>
#include <vector>
using namespace std;
int solution(int n) {
int answer = 0;
int count = 1;
int total = 0;
while(count <= n)
{
total = 0;
for(int i = count; i <= n; ++i)
{
total += i;
if(total >= n)
break;
}
if(total == n) answer++;
count++;
}
return answer;
}
또다른 풀이법:
1. 투 포인터 알고리즘
접근:
- 합을 유지하면서 범위를 조절합니다.
#include <string>
#include <vector>
using namespace std;
int solution(int n) {
int answer = 0;
int sum = 0;
int start = 1;
for (int end = 1; end <= n; end++) {
sum += end;
while (sum > n) {
sum -= start;
start++;
}
if (sum == n) {
answer++;
}
}
return answer;
}
2. 정수론(홀수 약수의 개수)
접근:
- 수학적으로 주어진 자연수 n을 연속된 자연수의 합으로 표현하는 방법의 수는 n의 홀수 약수의 개수와 같다는 정리를 이용합니다.
#include <string>
#include <vector>
using namespace std;
int solution(int n) {
int answer = 0;
for (int i = 1; i <= n; i++) {
if (n % i == 0 && i % 2 != 0) {
answer++;
}
}
return answer;
}