알고리즘 #12 (DP, 백준 2579번) [C++]

DP 두번째!

 

DP 초보자로서

https://zzonglove.tistory.com/13

동적계획법 (Dynamic Programming) 는 어떻게 풀까?

이 게시글의 동적계획법 푸는 순서을 한 번 따라해보려했다.

 

[백준 2579번]

https://www.acmicpc.net/problem/2579

2579번: 계단 오르기

계단 1개 → {1}

계단 2개 → {1, 2}, {2}

계단 3개 → {1, 3}, {2, 3}

계단 4개 → {1, 2, 4}, {1, 3, 4}, {2, 4}

계단 5개 → {1, 2, 4, 5}, {1, 3, 5}, {2, 3, 5}, {2, 4, 5}

...

 

규칙은 n개의 계단일 때 경우의 수가

n-2개의 계단의 경우의 수 + n-3개의 계단의 경우의 수 라는 것이었다.

이를 이용해서 n개의 계단일 때 계단의 수를 구하고 그 모든 경우의 수를 총점수를 계산한 후 sort해 최댓값을 구하는 방식으로 코드를 적어봤는데

#define _CRT_SECURE_NO_WARNINGS 1
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

void readScore(int& T,vector<int>& scores) {
	int score;
	cin >> T;
	for (int i = 0; i < T; i++) {
		cin >> score;
		scores.push_back(score);
	}
}

vector<vector<int>> nOrders(int n) {
	vector<vector<int>> orders;

	if (n == 0)
		orders = { { 1 } };
	else if (n == 1)
		orders = { { 1, 2 }, { 2 } };
	else if (n == 2)
		orders = { { 1, 3 }, { 2, 3 } };
	else {
		vector<vector<int>> n2 = nOrders(n - 2);
		vector<vector<int>> n3 = nOrders(n - 3);

		for (int i = 0; i < n2.size(); i++) {
			n2[i].push_back(n+1);
			orders.push_back(n2[i]);
		}
		for (int i = 0; i < n3.size(); i++) {
			n3[i].push_back(n);
			n3[i].push_back(n+1);
			orders.push_back(n3[i]);
		}
	}

	return orders;
}

int maxScore(vector<int> scores, vector<vector<int>> orders) {
	int totalScore = 0;
	vector<int> totalScores;
	for (int i = 0; i < orders.size(); i++) {
		for (int j = 0; j < orders[i].size(); j++) {
			totalScore += scores[orders[i][j]];
		}
		totalScores.push_back(totalScore);
		totalScore = 0;
	}
	sort(totalScores.begin(), totalScores.end());
	return totalScores[totalScores.size()-1];
}

int main() {
	int T, max;
	vector<vector<int>> orders;
	vector<int> scores = { 0 };
	
	readScore(T, scores);

	orders = nOrders(T - 1);
    
	max = maxScore(scores, orders);
	cout << max;
}

참.. 길다...

비주얼 스튜디오에서 몇가지 수로 돌려봤을 때 답이 정상적으로 출력됐다. 하지만...

ㅎㅎ... 역시 초보자에게는 호락호락하지 않다.

 

모를 땐 검색!

항상 느끼지만 정말 잘하시는 분, 똑똑한 분들이 너무 많다..... 

https://yabmoons.tistory.com/20

[ 백준 2579 ] 계단오르기 (C++)

이 분의 코드를 따라하면서 공부했다.

하면서 내 코드가 얼마나 불필요하게 나뉘었는지 정말 많이 느꼈다ㅎ

 

#define _CRT_SECURE_NO_WARNINGS 1
#include <iostream>
#include <vector>
#define MAX 301

using namespace std;

int T;
int maxScores[MAX];
int scores[MAX];

int Max(int A, int B) { if (A > B) return A; return B; }

void readScore() {
	cin >> T;
	for (int i = 1; i <= T; i++) {
		cin >> scores[i];
	}
}

void maxSum() {
	maxScores[1] = scores[1];
	maxScores[2] = scores[1]+scores[2];
	maxScores[3] = Max(scores[1] + scores[3], scores[2] + scores[3]);

	for (int i = 4; i <= T; i++) {
		maxScores[i] = Max((maxScores[i - 2] + scores[i]), (maxScores[i - 3] + scores[i - 1] + scores[i]));
	}

	cout << maxScores[T];
}

int main() {
	readScore();
	maxSum();
}

길이가 확줄었다^^ㅋㅋㅋㅋ

효율적이고 깔끔한 코드다... 진짜 열심히 배워야지...