글 읽기 - 안녕하세요 정답은 맞췃는데 질문이 있어서요

pch1623 3년 전 0

제 코드중 func 함수안에 1빼는 부분에서

if (n > 1 && (arr[n - 1] == 0 || arr[n - 1] > cnt + 1)) 이 코드를

if (n > 1) 이렇게 바꾸면 아예 출력이 안되더라구요 왜그런걸까요 ??

if (arr[n] > cnt || arr[n] == 0)
arr[n] = cnt;

바로위 쪽에 이 코드에서 예외를 다 잡아주지 못하는 건가요 ? ?

#include<iostream>
#include<algorithm>
using namespace std;

int N;

int arr[2000];

void func(int n, int cnt, int copy) {

	if (arr[n] > cnt || arr[n] == 0)
		arr[n] = cnt;

	//1빼기
	if (n > 1 && (arr[n - 1] == 0 || arr[n - 1] > cnt + 1))
		func(n - 1, cnt + 1, copy);


	//붙여넣기
	if (n + copy < 2000 && copy > 0 )
		func(n + copy, cnt + 1, copy);


	//모두 복사해서 붙여넣기
	if (n + n < 2000 && n > 0 )
		func(n + n, cnt + 2, n);

}



int main() {
	cin >> N;
	arr[1] = 1;
	func(2, 2, 1);
	cout << arr[N];

}

line_jin 3년 전 1

cnt값이 갱신되지 않을 경우 해당 상태에서 더 진행할 필요가 없기에 return해주어야 합니다.

그렇지 않을 경우 무한 재귀를 돌아버려요

ex) n : 1 -> n : 2 -> n -> 1 .......

	if (arr[n] > cnt || arr[n] == 0)
		arr[n] = cnt;
	else
		return;

pch1623 3년 전 0

감사합니다 ㅎㅎ

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

문제

문제

출처

ICPC

안녕하세요 정답은 맞췃는데 질문이 있어서요

pch1623 3년 전 0

line_jin 3년 전 1

pch1623 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말