글 읽기 - 14501번 퇴사 문제 메모리 초과..

ygy5315 3년 전 1

14501번 퇴사문제를 재귀함수 호출을 통해서 해당 일자를 선택하거나 스킵하고 다음 일자를 택해서 금액의 최대를 구하도록 풀었습니다.

다만 메모리 초과가 일어나서..... 혹시 어떻게 해야 줄일 수 있을지 조언을 구합니다!!

추가적으로 코딩 문제를 DFS 혹은 BFS로 풀경우 메모리 크기 계산은

다들 어떻게 계산하시는지 알수 있을까요?

저는 메로리 양은 거의 고려하지 않고 계산횟수로 1초 = 약 1억번 계산으로 해서 접근하는데..

메모리 초과 문제는 어떻게 계산 잡고 갈지 여쭙습니다!!

끝으로 긴글 읽어주셔서 감사드립니다!!

//14501번퇴사

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>

#define BIGGER(a, b) (a)>(b)?(a):(b)
#define MAX 20
using namespace std;

//  0     1
// 시간  비용
int TC[MAX][2] = { 0, };
int N=0;
int res = 0;
int visited[MAX] = { 0, };

void DFS(int index, int money){

	if (index <= N){
		if ((index == N - 1) && (TC[index-1][0] == 1)){
			res = BIGGER(res, money+TC[index-1][1]);
		}
		res = BIGGER(res, money);
	}
	else{
		return;
	}

	if (index >= N) return;

	DFS(index + TC[index][0], money + TC[index][1]);

	DFS(index + 1, money);
	

}

int main(){

	ios::sync_with_stdio(0);
	cin.tie();
	cout.tie();

	scanf("%d", &N);

	for (int y = 0; y < N; y++){
		for (int x = 0; x < 2; x++){
			cin >> TC[y][x];
		}
	}

	DFS(0, 0);

	cout << res;

	return 0;
}

djm03178 3년 전 2

이렇게 입력량도 작고 배열도 엄청 작을 수밖에 없는 문제에서 메모리 초과가 났다면 메모리 사용량을 '줄이는' 것이 문제가 아니라, 어딘가 프로그램이 크게 잘못 동작하고 있다고 생각해야 합니다.

sync_with_stdio(0);을 한 이후에는 C와 C++의 입출력 방식을 섞어쓰면 안 되는데 44번째 줄에서는 scanf를 쓰고 48번째 줄에서는 cin을 쓰고 있다는 것이 문제입니다.

이와는 별개로, cin.tie();는 아무런 의미가 없는 문장입니다. cin.tie(0);이라고 인자를 전달해야 의미가 있습니다.

cout.tie는 인자가 있든 말든 아무 의미가 없는 문장입니다.

ygy5315 3년 전 0

cin.tie(0)으로 쓰고 모든 입력을 cin으로 받아서 돌리니 해결했습니다.

추가적으로 test_case 디버깅 과정 중,

if (index <= N){
if ((index == N ) && (TC[index-1][0] == 1)){
res = BIGGER(res, money);
}
res = BIGGER(res, money);
}

마지막 끝 조건에서 이전 배열 값을 갱신하는 문제가 있었네요. 위코드로 수정해서 메모리 초과없이 통과했습니다.

바쁘실텐데 읽어주셔서 감사드리고 친절한 답변에 또한번 감사드립니다!!

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

문제

문제

출처

ICPC

14501번 퇴사 문제 메모리 초과..

ygy5315 3년 전 1

djm03178 3년 전 2

ygy5315 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말