[Algorithm][C++] JUNGOL 4197: swat. 연습실

url: http://jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=3547&sca=99 

JUNGOL

 

풀이 핵심

1. BackTracking / Bruth Force 문제 (재귀 함수 완전 탐색)

 

2. 현재 날짜를 선택 하냐 / 안하냐 로 재귀 함수 만들어 주면 끝...

 

코드

#define _CRT_SECURE_NO_WARNINGS
#include <cstdio>

int N, ans;
struct INFO{ int time, pay; };
INFO schedule[15]; // 수업 시간, 페이에 대한 정보 (index가 날짜, 0부터 시작)

void solve(int day, int sum) {
	if (day == N) { // day가 N이라는 것은 여행 가는날 ~
		if (ans < sum) {
			ans = sum;
		}
		return;
	}
	if (day > N) return; // day가 N 보다 크면 어떤 수업을 다 못 끝낸 것..

	solve(day + schedule[day].time, sum + schedule[day].pay); // 오늘 수업 함
	solve(day + 1, sum); // 오늘 수업 안함
}

int main() {
	scanf("%d", &N);
	for (int i = 0; i < N; i++) {
		int t, p;
		scanf("%d %d", &schedule[i].time, &schedule[i].pay);
	}
	solve(0, 0);
	printf("%d", ans);
	return 0;
}

 

이 문제를 어디서 풀어봤더라.. 정말 비슷한 문제를 풀었던 것 같은데 뭔지 기억이 안난다..

무튼 쉬운 문제인 것 같다.