1R/2016 09 25 - Revision history

Maintenance script: Repair pages found by live-compare batch 0001

2026-03-26T14:46:15Z

Repair pages found by live-compare batch 0001

← Older revision		Revision as of 14:46, 26 March 2026
Line 14:		Line 14:

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

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

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

	int main() {		int main() {
Line 57:		Line 57:
	}		}

	dp[0].push_back(0);		dp[0].push_back(0);
	dp[0].push_back(st[1]);		dp[0].push_back(st[1]);
	dp[1].push_back(st[0]);		dp[1].push_back(st[0]);
	dp[1].push_back(st[0] + st[1]);		dp[1].push_back(st[0] + st[1]);

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

	std::cout << std::max(dp[0][n - 1], dp[1][n - 1]);		std::cout << std::max(dp[0][n - 1], dp[1][n - 1]);
	return 0;		return 0;
	}		}
Line 83:		Line 83:
	== 박인서 ==		== 박인서 ==
	* Dynamic Programming		* Dynamic Programming
	* dp[k][i] - i번째 계단까지 오르는데 그 직전에 밑계단에서 올라왔다면 k=1, 아니면 k=0이다.		* dp[k][i] - i번째 계단까지 오르는데 그 직전에 밑계단에서 올라왔다면 k=1, 아니면 k=0이다.
	* dp[0][i] = max(dp[0][i-2],dp[1][i-2])+st[i]		* dp[0][i] = max(dp[0][i-2],dp[1][i-2])+st[i]
	* dp[1][i] = dp[1][i-1]+st[i]		* dp[1][i] = dp[1][i-1]+st[i]

	== 곽정흠 ==		== 곽정흠 ==

219.255.207.30 at 03:34, 28 September 2016

2016-09-28T03:34:08Z

← Older revision		Revision as of 03:34, 28 September 2016
Line 83:		Line 83:
	== 박인서 ==		== 박인서 ==
	* Dynamic Programming		* Dynamic Programming
	* dp~~[j][~~i~~]~~ - i번째 계단까지 오르는데 그 직전에 밑계단에서 올라왔다면 j=1, 아니면 j=0이다.		* dp[k][i] - i번째 계단까지 오르는데 그 직전에 밑계단에서 올라왔다면 k=1, 아니면 k=0이다.
	* dp~~[~~0~~][~~i~~]~~=max(dp~~[~~0~~][~~i-2~~]~~,dp~~[~~1~~][~~i-2~~]~~)+st~~[~~i~~]~~		* dp[0][i] = max(dp[0][i-2],dp[1][i-2])+st[i]
	* dp~~[~~1~~][~~i~~]~~=dp~~[~~1~~][~~i-1~~]~~+st~~[~~i~~]~~		* dp[1][i] = dp[1][i-1]+st[i]

	== 곽정흠 ==		== 곽정흠 ==

219.255.207.30 at 03:33, 28 September 2016

2016-09-28T03:33:30Z

@@ Line 42: / Line 42: @@
+  }
 == 박인서 ==
 == 곽정흠 ==
@@ Line 52: / Line 80: @@
 * 2번 밟은 상태는 밑 계단에서 1계단 오른 것입니다. 이는 3번 연속 밟는 것과 상관이 있으므로 밑 계단에서 1번 밟은 상태의 값에 현 계단의 값을 더하여 2번 밟은 상태에 저장합니다.
 * 이를 반복하여 끝 계단의 1번 밟은 상태와 2번 밟은 상태의 값 중 큰 값을 출력합니다.
 == 박인서 ==
 == 곽정흠 ==

175.124.46.11: {CREATE}

2016-09-26T16:05:00Z

{CREATE}

New page

__TOC__

= 오늘의 문제 =
* [https://www.acmicpc.net/problem/2579|계단 오르기]

= 참가자 =
* 15이원준
= 코드 =
== 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;
}
== 박인서 ==

== 곽정흠 ==

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

== 곽정흠 ==