반응형
250x250
Notice
Recent Posts
Recent Comments
Link
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | ||
6 | 7 | 8 | 9 | 10 | 11 | 12 |
13 | 14 | 15 | 16 | 17 | 18 | 19 |
20 | 21 | 22 | 23 | 24 | 25 | 26 |
27 | 28 | 29 | 30 | 31 |
Tags
- 코딩테스트
- 최대값과 최솟값
- netmode
- unity
- C++
- fruitspuzzle
- pccp 기출문제
- 당구 연습
- 프로그래머스
- 2018 kakao
- network model
- 리플렉션 시스템
- 로컬 네트워크 연결
- 구현
- 2022 kakao
- 프로젝트
- 백준
- ai controller
- enetrole
- Algorithm
- Unreal Engine
- issac3d
- unrealengine
- Summer/Winter Coding
- timelessadventure
- gameinstancesubsystem
- pcce 기출문제
- fabrik ik
- 2019 kakao
- c#
Archives
- Today
- Total
LeeTaes 공부노트
[프로그래머스/C++ 문제 풀이] Lv. 2 - 숫자의 표현 본문
728x90
반응형
문제 설명
Finn은 요즘 수학공부에 빠져 있습니다. 수학 공부를 하던 Finn은 자연수 n을 연속한 자연수들로 표현 하는 방법이 여러개라는 사실을 알게 되었습니다. 예를들어 15는 다음과 같이 4가지로 표현 할 수 있습니다.
- 1 + 2 + 3 + 4 + 5 = 15
- 4 + 5 + 6 = 15
- 7 + 8 = 15
- 15 = 15
자연수 n이 매개변수로 주어질 때, 연속된 자연수들로 n을 표현하는 방법의 수를 return하는 solution를 완성해주세요.
제한 사항
- n은 10,000 이하의 자연수 입니다.
입출력 예
입출력 예#1
문제의 예시와 같습니다.
문제 풀이
저는 이번 문제를 보며 연속되는 수의 합을 비교하는 문제이기에 누적합을 사용하면 좋을 것 같다고 생각하게 되었습니다.
누적합을 사용해 n이 5인 경우의 예시를 들어보면 다음과 같습니다.
위와 같이 누적합을 구해둔 상황에서 두 인덱스의 차가 n이 나오는지 확인해보면 간단히 해결할 수 있습니다.
low 인덱스가 0이고, high인덱스가 1인 경우 psum[high] - psum[low] = 1입니다.
계산을 통해 나온 숫자가 n보다 작으므로 high인덱스를 우측으로 1칸 옮겨주고 다시 계산을 반복합니다.
(만약 계산을 통해 나온 숫자가 n보다 큰 경우라면 low인덱스를 우측으로 옮겨주면 됩니다.)
위의 예시에서 계산 결과가 5가 나오는 경우는 2가지(3, 1), (5, 4)가 존재하며 실제 연속된 수의 합으로 5를 만드는 방법 또한 2가지 (2 + 3, 5)만이 존재하는 것을 확인할 수 있고, 해당 방법을 통해 이번 문제를 해결하였습니다.
정답 코드
더보기
풀이 시간 : 7m 22s
#include <string>
#include <vector>
using namespace std;
int psum[10003];
int solution(int n) {
int answer = 0;
// 누적합을 구해주도록 합니다.
psum[0] = 0;
for (int i = 1; i <= n; i++)
{
psum[i] = i + psum[i - 1];
}
// 누적합의 차를 이용해 n을 만들어 줄 예정입니다.
// * 두개의 인덱스를 준비합니다.
int lowIdx = 0;
int highIdx = 1;
while(true)
{
// 만약 오른쪽의 인덱스가 n을 벗어나는 경우 중단합니다.
if (highIdx > n) break;
// 누적합의 두 인덱스 차와 n과의 관계를 비교하여 인덱스를 조절합니다.
if (psum[highIdx] - psum[lowIdx] > n)
{
lowIdx++;
}
else if (psum[highIdx] - psum[lowIdx] < n)
{
highIdx++;
}
// 두 값의 차가 n인 경우
else
{
// 만들 수 있는 쌍의 수를 증가시키고, 우측 인덱스를 한 칸 움직입니다.
answer++;
highIdx++;
}
}
return answer;
}
728x90
반응형
'코딩테스트 > 프로그래머스 (Lv. 2)' 카테고리의 다른 글
[프로그래머스/C++ 문제 풀이] Lv. 2 - 피보나치 수 (0) | 2024.08.23 |
---|---|
[프로그래머스/C++ 문제 풀이] Lv. 2 - 다음 큰 숫자 (0) | 2024.08.23 |
[프로그래머스/C++ 문제 풀이] Lv. 2 - 이진 변환 반복하기 (0) | 2024.08.23 |
[프로그래머스/C++ 문제 풀이] Lv. 2 - JadenCase 문자열 만들기 (0) | 2024.08.19 |
[프로그래머스/C++ 문제 풀이] Lv. 2 - 최솟값 만들기 (0) | 2024.08.19 |