글 읽기 - 고수분들의 도움이 필요할것 같습니다.

cleankid99 5년 전 0

안녕하세요? DFS로 문제를 풀었고,

문제에 있는 예제와 질문게시판에 있는 반례들을 통해서

대부분을 다 구현한것같은데

아무래도 제가 보지 못하는 영역을 넘어서는 부분에 예외가 존재하는거같아요

DFS로 완전탐색을 구현한건데 어디서 문제가 생기는지 잘 모르겠습니다..!

코드에 주석 달아놓았어요!!

#include <iostream>
using namespace std;

int n, best = 0;
int time[16];
int price[16];

void dfs(int idx, int val) {
	if (idx + time[idx] > n + 1 || idx > n) { // idx + time[idx] 가 n+1을 넘거나, idx 자체가 n 보다 크거나
		if (best < val) {
			best = val;
		}
		return;
	}
	dfs(idx + time[idx], val + price[idx]); // 포함된 경우
	dfs(idx + 1, val); // 포함 안되면 idx는 하나만 증가시킴
}


int main() {
	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> time[i] >> price[i];
	}
	
	for (int i = 1; i <= n; i++) { // 반복문을 통해 시작위치를 바꿔줌으로써 완전탐색 실행
		dfs(i, 0);
	}
	
	cout << best << '\n';

	return 0;
}

0_o 5년 전 2

DFS의 첫번째 if문에서 idx > n을 idx + time[idx] > n + 1 앞으로 옮겨야 합니다.

idx가 n보다 커지면, idx + time[idx]가 idx + price[idx-n]와 같아집니다.

그 이유는 time 배열 바로 뒤에 price 배열을 선언했기 때문에

[(time 배열)][(price 배열)] 와 같은 형태로 time 배열 과 price배열이 붙어서 저장됩니다.

그래서 time에서 범위를 넘어간 인덱스값을 넣으면 price배열을 보기 시작합니다.

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

문제

문제

출처

ICPC

고수분들의 도움이 필요할것 같습니다.

cleankid99 5년 전 0

0_o 5년 전 2

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말