U E D R , A S I H C RSS

1R/2016_09_25



1. 오늘의 문제

2. 참가자

  • 15이원준

3. 코드

3.1. 15이원준

#include<iostream>
#include<algorithm>

using namespace std;

int N;
int arr[301] = { 0, };
int dp[301][3] = { 0, };

int main(){
    cin>> N;
    for(int i = 1; i<=N; i++){
      scanf("%d", &arr[i]);
    }
    if(N < 3){
      int ans = 0;
      for(int i = 1; i<=N; i++){
        ans += arr[i];
      }
      cout<< ans << endl;
      return 0;
    }
    dp[1][1] = arr[1];
    dp[2][1] = arr[2];
    dp[2][2] = dp[1][1] + arr[2];
    for(int i = 3; i<=N; i++){
      dp[i][1] = max(dp[i-2][1], dp[i-2][2]) + arr[i];
      dp[i][2] = dp[i-1][1] + arr[i];
    }
    int ans = 0;
    ans = max(dp[N][2] , dp[N][1]);
    cout<< ans <<endl;
}

3.2. 박인서

#include <iostream>
#include <vector>
#include <algorithm>

std::vector<int> dp[2], st;

int main() {
	int n;
	std::cin >> n;
	for (int i = 0; i < n; i++) {
		int t;
		std::cin >> t;
		st.push_back(t);
	}

	dp[0].push_back(0);
	dp[0].push_back(st[1]);
	dp[1].push_back(st[0]);
	dp[1].push_back(st[0] + st[1]);
	
	for (int i = 2; i < n; i++) {
		dp[0].push_back(std::max(dp[0][i - 2], dp[1][i - 2]) + st[i]);
		dp[1].push_back(dp[0][i - 1] + st[i]);
	}

	std::cout << std::max(dp[0][n - 1], dp[1][n - 1]);
	return 0;
}

3.3. 곽정흠


4. 아이디어

4.1. 15이원준

  • dp를 이용하여 풀었습니다.
  • 각 계단의 상태는 연속해서 1번 밟은 상태이거나 2번 밟은 상태일 수있습니다.
  • 1번 밟은 상태는 밑밑 계단에서 2계단 오른 것입니다. 이는 3번연속 밟는 것과 상관이 없으므로 밑밑 계단에서 두 상태 중 더 큰 값을 갖는 것을 가져와 현 계단의 값을 더여 1번 밟은 상태에 저장합니다.
  • 2번 밟은 상태는 밑 계단에서 1계단 오른 것입니다. 이는 3번 연속 밟는 것과 상관이 있으므로 밑 계단에서 1번 밟은 상태의 값에 현 계단의 값을 더하여 2번 밟은 상태에 저장합니다.
  • 이를 반복하여 끝 계단의 1번 밟은 상태와 2번 밟은 상태의 값 중 큰 값을 출력합니다.

4.2. 박인서

  • Dynamic Programming

 * dp[k][i] - i번째 계단까지 오르는데 그 직전에 밑계단에서 올라왔다면 k=1, 아니면 k=0이다.
 * dp[0][i] = max(dp[0][i-2],dp[1][i-2])+st[i]
 * dp[1][i] = dp[1][i-1]+st[i]

4.3. 곽정흠

Valid XHTML 1.0! Valid CSS! powered by MoniWiki
last modified 2021-02-07 05:22:07
Processing time 0.0204 sec