11052 실버 1) 카드 구매하기 DP

 

풀이: 배열에 순서대로 입력받고 for문을 1부터 n까지 와 i * j 를 n까지 이중 포문을 돌림

배열의 arr[i * j] 값과 arr[i]  * j 중 더 큰 값을 arr[i * j]에 대입한다

대입을 해주는 이유는 1개에 10원 하는것을 4개씩 파는 것과 4묶음에 30원짜리에 파는 것 중 더 비싸게 살 수 있는 

경우를 생각하여야 합니다.

 

그리고 두번째 이중 포문에서는  만약 내가 3개에  20원에 사는 것과 2개에 15원, 1개에 10원짜리를 같이 사는 것 중

어느 것이 더 비싸게 살 수 있는지에 대한 대입을 해주는 코드입니다.

 

GPT를 활용하여 주석을 달았습니다.

#include <iostream>
#include <algorithm>

using namespace std;

int main() {
    int n;
    
    // 입출력 속도 향상을 위한 설정
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
    // n 입력 받기
    cin >> n;
    
    // 배열 초기화 (배열의 크기는 1001, 모든 값은 0으로 초기화)
    int arr[1001] = {0,};
    
    // 1부터 n까지의 값을 입력 받음
    for(int i = 1; i <= n; i++) {
        cin >> arr[i];
    }
    
    // 첫 번째 이중 for문: arr 배열의 값들을 갱신
    // i는 1부터 n까지, i * j가 n 이하일 때까지 j를 증가시키며 배열 갱신
    // arr[i * j]는 arr[i * j]와 arr[i] * j 중 큰 값으로 갱신됨
    for(int i = 1; i <= n; i++) {
        for(int j = 2;  i * j <= n; j++) {
            arr[i * j] = max(arr[i * j], arr[i] * j);
        }    
    }
    
    // 두 번째 이중 for문: arr 배열의 값들을 재갱신
    // i를 2부터 n까지 증가시키며, i를 j와 (i-j)로 분할했을 때 값의 합이 더 큰지 비교
    for(int i = 2; i <= n; i++) {
        for(int j = 1; j <= i / 2; j++) {
            arr[i] = max(arr[i], arr[j] + arr[i - j]);
        }
    }
    
    // n번째 인덱스에 저장된 값 출력
    cout << arr[n];
}