글 읽기 - 고수님들 바쁘신 거 알지만 한번만 도와주십시오

mywonkim 3년 전 0

제가 코드를 짜긴 했는데 효율적으로 짠 건지 잘 모르겠습니다. 점화식 구하고 bottomup으로 한다고 했는데 효율적인 코드가 맞을까요?

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n;
    cin >> n;
    if (n == 1) {
    	cin >> n;
    	cout << n;
    	return 0;
	}
    vector<int> wine(n);
    vector<vector<int> > dp(n, vector<int>(3, 0));
    for (int i = 0; i < n; ++i) {
        cin >> wine[i];
    }
    dp[0][1] = wine[0];
    dp[1][1] = wine[1];
	dp[1][2] = wine[0] + wine[1];
    for (int i = 2; i < n; ++i) {
        for (int j = 0; j <= 2; ++j) {
        	if (j == 2) {
        		dp[i][j] = dp[i - 1][1] + wine[i];
			}
            else if (j == 1) {
                dp[i][j] = max({dp[i - 1][0] + wine[i],
								dp[i - 2][0] + wine[i],
                				dp[i - 2][1] + wine[i],
								dp[i - 2][2] + wine[i]});
            }
            else {
                dp[i][j] = max({dp[i - 1][2],
								dp[i - 1][1],
                				dp[i - 1][0],
								dp[i - 2][2],
								dp[i - 2][1],
								dp[i - 2][0]});
            }
        }
    }
    cout << max({dp[n - 1][0], dp[n - 1][1], dp[n - 1][2],
				 dp[n - 2][0], dp[n - 2][1], dp[n - 2][2]}) << "\n";
}

djm03178 3년 전 1

효율적이라는 게 시간 복잡도 측면을 말씀하시는 거라면 최적입니다.

mywonkim 3년 전 0

감사합니다!

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

고수님들 바쁘신 거 알지만 한번만 도와주십시오

mywonkim 3년 전 0

djm03178 3년 전 1

mywonkim 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말