글 읽기 - 계단 오르기 질문드려요....

charmant90 8년 전 0

DP는 잘 몰라서...

환형 큐를 이용해서 가볼 수 있는 모든 경우를 다 탐색하여 최대 값을 뽑아내는 것으로 코드를 작성했습니다.

index가 N 값이 넘어가면 큐에 넣지 못하게 함으로써 탈출 조건을 완성시켰습니다.

틀린 예시를 잘 모르겠습니다...

#include <iostream>
#define SIZE 1000000
using namespace std;

typedef struct {
	int jump, idx, sum;
} Data;

int arr[301];
Data queue[SIZE];

int N;
int Max;
int front, rear;

void inqueue(Data data) {
	rear = (rear + 1) % SIZE;
	queue[rear] = data;
}

Data dequeue() {
	front = (front + 1) % SIZE;
	return queue[front];
}

void start() {
	Data first = { 0, 1, arr[1] };
	inqueue(first);

	while (front != (rear + 1) % SIZE) {
		Data curr = dequeue();

		if (curr.idx == N) {
			if (Max < curr.sum)
				Max = curr.sum;
		}

		if (curr.idx == 1) {
			Data next;

			next = { 1, curr.idx + 1, curr.sum + arr[curr.idx + 1] };
			inqueue(next);

			next = { 2, curr.idx + 2, curr.sum + arr[curr.idx + 2] };
			inqueue(next);
		}
		else {
			Data next;

			if (curr.jump == 1) {
				if (curr.idx + 2 <= N) {
					next = { 2, curr.idx + 2, curr.sum + arr[curr.idx + 2] };
					inqueue(next);
				}
			}
			else {
				if (curr.idx + 1 <= N) {
					next = { 1, curr.idx + 1, curr.sum + arr[curr.idx + 1] };
					inqueue(next);
				}

				if (curr.idx + 2 <= N) {
					next = { 2, curr.idx + 2, curr.sum + arr[curr.idx + 2] };
					inqueue(next);
				}
			}
		}
	}
}

int main() {
	cin >> N;
	for (int i = 1; i <= N; i++) cin >> arr[i];

	start();
	cout << Max << endl;

	return 0;
}

hihihi 8년 전 0

큐의 최대 사이즈가 1000000인데 나올 수 있는 경우의 수는 그것보다 훨씬 커서 아닐까요 ?

indioindio 8년 전 0

입력이 60개 정도 되면 0을 출력하네요 큐의 사이즈를 약 5배 정도 늘려야 60개일 때 정답을 출력합니다.

charmant90 8년 전 0

// hihihi

환형 큐라.. 큐 사이즈를 저정도 잡으면 모든 경우의 수에 대해서 처리를 할 수 있을 것 같은데... 입력이 300개 들어오면 1000000개 보다 경우의 수가 많긴하지만...

음 사이즈 문제라면 일단 경우의 수가 몇가지 나올런지 계산을 다시 해봐야 겠습니다. 감사합니다.

// indioindio

저는 입력 100개로 테스트 했을 때도 정상적으로 값은 출력되었는데... 60개로 하니 또 0이 나오네요...

이 방법은 아닌 것 같습니다... 감사합니다.

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

문제

문제

출처

ICPC

계단 오르기 질문드려요....

charmant90 8년 전 0

hihihi 8년 전 0

indioindio 8년 전 0

charmant90 8년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말