«   2022/10   »
            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          
Archives
Today
0
Total
96,326
관리 메뉴

차근차근

[백준 1699] 제곱수의 합 본문

대학교/Algorithm

[백준 1699] 제곱수의 합

SWKo 2020. 2. 15. 01:57

0. 제목

  • 백준 1699 제곱수의 합
  • BOJ 1699 제곱수의 합
  • C++ 1699 제곱수의 합

1. 문제

https://www.acmicpc.net/problem/1699


2. 풀이

  • dp방식을 사용하였다.
  • 먼저 dp의 각 원소들을 1로만 이루어진 개수로 초기화시켰다.
  • 이중반복문에서 i와 j는 1부터 시작할 필요가 없다. 이유는 dp[i] = i 여기서 초기화를 했는데 모두 1로 이루어진 경우를 나타낸 것이다. 따라서 2부터 시작해도 상관이 없다. 오히려 더 빠르다.
  • dp[i] = min(dp[i], dp[i-j*j] + 1); 이 부분은 dp[i] 즉, 초기에 설정했던 값과 dp[i-j*j]+1 중 최솟값을 고르는 것이다.
  • dp[i-j*j] 에 1을 더해주는 이유는 j*j에서 항이 1개 나오기 때문이다.
  • 그리고 j가 2부터 i*i 보다 작거나 같은 동안 반복하기 때문에 최솟값이 계속 갱신될 수 있다.
  • 반복문이 끝나고 나면 dp[1]부터 dp[N] 까지의 값이 모두 구해진다.

3. 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <iostream>
#include <algorithm>
using namespace std;
 
int N;
int dp[100001];
 
int main(int argc, const char * argv[]) {
    cin >> N;
    
    for(int i = 1; i <= N; i++)
        dp[i] = i;
    
    for(int i = 2; i <= N; i++)
        for(int j = 2; j*<= i; j++)
            dp[i] = min(dp[i], dp[i-j*j] + 1);
            
    cout << dp[N] << '\n';
    return 0;
}
 
 

'대학교 > Algorithm' 카테고리의 다른 글

[백준 1966] 프린터 큐  (0) 2020.02.16
[백준 2170] 선 긋기  (0) 2020.02.15
[백준 1149] RGB거리  (0) 2020.02.13
[백준 11650] 좌표 정렬하기  (0) 2020.02.13
[백준 2751] 수 정렬하기 2  (0) 2020.02.13
0 Comments
댓글쓰기 폼