Search
Duplicate
🍋

카드 구매하기

주차
11
문제번호
11052
언어
티어
실버
유형
DP
nj_Blog
nj_상태
이해도
풀이
풀이 O
사람
13 more properties

Memo

풀이
두가지 풀이를 생각해 보았는데 로직상으로 다른점은 없다.
입력을 우선적으로 다 받고 로직을 돌리는 것과 입력을 받으면서 연산을 하는 것 중 어떤 것이 더 좋은 코드인지 고민을 해보기 위해서 작성해 보았다.

Code

제출 날짜

@2/23/2021

메모리

2016 KB

시간

0 ms

< 풀이 1 >

input vector를 받은 후 dp vector 처리
#include <iostream> #include <vector> int N; std::vector<int> arr; std::vector<int> dp; void output() { std::cout << dp[N]; } void solution() { for (int i = 1 ; i <= N ; i++) { for (int j = 1 ; j <= i ; j++) dp[i] = std::max(dp[i], dp[i - j] + arr[j]); /************출력용************* for (int k = 1 ; k <= N ; k++) std::cout << dp[k] << " "; std::cout << std::endl; ***************************/ } } void input() { std::cin >> N; arr.resize(N + 1); dp.resize(N + 1); for (int i = 1 ; i <= N ; i++) std::cin >> arr[i]; } void preset() { std::ios_base::sync_with_stdio(false); std::cin.tie(NULL); std::cout.tie(NULL); } int main() { preset(); input(); solution(); output(); }
C++
복사

< 풀이 2 >

input 을 받는 위치에서 바로 dp vector 연산
#include <iostream> #include <vector> int N; std::vector<int> arr; std::vector<int> dp; void output() { std::cout << dp[N]; } void input_sol() { std::cin >> N; arr.resize(N + 1); dp.resize(N + 1); for (int i = 1 ; i <= N ; i++) { std::cin >> arr[i]; for (int j = 1 ; j <= i ; j++) dp[i] = std::max(dp[i], dp[i - j] + arr[j]); } } void preset() { std::ios_base::sync_with_stdio(false); std::cin.tie(NULL); std::cout.tie(NULL); } int main() { preset(); input_sol(); output(); }
C++
복사