일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
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 |
- 조건문
- 반복문
- 패스트캠퍼스혁펜하임
- 혁펜하임강의후기
- 1로만들기
- c++ 기초
- 혁펜하임강의
- 비교연산자
- 패스트캠퍼스
- 백준1463
- AIDEEPDIVE
- 혁펜하임
- 백준
- pytorch
- precision
- 백준1026
- C++ 백준
- CUDA
- C++
- for문
- cuDNN
- 백준C++
- C++ 함수
- C++ 공백 입력
- 1463
- 혁펜하임AI
- AI강의
- 9095
- 백준9095
- tensorflow
- Today
- Total
코딩하는 덕구 🐶
72. C++ 백준 1789번 수들의 합 자세한 설명 본문
안녕하세요 코딩하는 덕구입니다.
그리디 알고리즘 문제인 수 들의 합 C++ 백준 1789번 입니다.
https://www.acmicpc.net/problem/1789
1789번: 수들의 합
첫째 줄에 자연수 S(1 ≤ S ≤ 4,294,967,295)가 주어진다.
www.acmicpc.net
N개의 자연수의 합 S가 주어질 때 N의 최대값을 묻는 문제이므로
최대한 작은 수들의 합이 S 가 되면 되겠죠.
1부터 n까지의 합은 n * (n +1)/2 입니다.
3가지의 경우가 있습니다.
1. S보다 1부터 n까지의 합이 작다면 S = n(n+1)/2 을 만족시키지 못하므로 n을 증가시킵니다.
2. S보다 1부터 n까지의 합이 S 와 같다면 n은 S를 만들기 위한 N의 최대값이 되고
3. S보다 1부터 n까지의 합이 S보다 크다면 (n을 1씩 증가시키면서 n * (n +1)/2 을 만들었을 때)
n * (n -1)/2 이 S보다 작고, n(n+1)/2 가 S 보다 크다는 말과 같고
첫번째 식에서 n을 더했을 때 S 보다 커지게 되므로
n보다 작고 S = n(n+1)/2 - x 를 만족하는 수 x가 지금까지의 합에 존재한다는 것을 알 수 있습니다.
즉 S가 주어질 때 N의 최대값은 n - 1개가 되죠
위 직관으로 코드를 작성해봅시다.
1부터 N까지의 합이 S 보다 작다면 N 을 1부터 1개씩 증가시키면서, 계속 비교하고
int N = 1;
while ( 1 ){
sum += N;
if (sum > S) break;
N++;
}
1을 빼서 출력해주면 됩니다.
cout << N - 1;
아래와 같이 합의 공식을 써서 작성을 해보았더니
while ( N(N+1)/2 < S ){
시간 초과가 나서 매번 n을 두번 곱하는 연산이 아닌
처음과 같은 방법을 사용 했습니다.
수 들의 합 백준 1789번 C++ 최종 코드입니다.
#include <iostream>
using namespace std;
int main(){
cin.tie(0);
cout.tie(0);
ios::sync_with_stdio(0);
long long S, sum = 0;
int N = 1;
cin >> S;
while ( 1 ){
sum += N;
if (sum > S) break;
N++;
}
cout << N - 1;
return 0;
}
제가 운영하는 오픈 카톡방입니다. 알고리즘, 코딩, 취업정보 등 자유롭게 질문, 답변 및 대화 나눠요.
https://open.kakao.com/o/guGhqGAg
알고리즘, 코딩, 개발자 취업 질문방 (비번 4321)
#코딩 #개발자 #알고리즘 #코테 #코딩테스트 #질문 #개발직군취업 #SW #SW취업
open.kakao.com
수 들의 합 백준 1789번 C++ 자세한 설명이었습니다. 감사합니다.
'알고리즘 문제 풀이' 카테고리의 다른 글
74. C++ 백준 2667 단지 번호 붙이기 자세한 설명 (1) | 2023.01.11 |
---|---|
73. Python 백준 2667 단지 번호 붙이기 자세한 설명 (0) | 2023.01.10 |
71. Python 백준 1789 번 수들의 합 자세한 설명 (0) | 2023.01.08 |
70. C++ 백준 2606 번 바이러스 자세한 설명 (0) | 2023.01.05 |
69. Python 백준 2606 번 바이러스 자세한 설명 (0) | 2023.01.05 |