글 읽기 - 재귀호출로는 해결을 못하네요. 도움 주세요.

hjj5612 3년 전 0

재귀호출로 하니 a와 s 그리고 b와 s 차가 너무 큰 경우에는 stack overflow가 발생하네요. 그리고 속도도 너무 느리네요. 어떤 좋은 방법으로 이것을 해결할 수 있을까요? 도움 주세요.

import java.util.*;

public class Main {
	private static long a, b, s;
	
	private static boolean input() {
		boolean status;
		
		try(Scanner kb = new Scanner(System.in)) {
			a = kb.nextLong();
			b = kb.nextLong();
			s = kb.nextLong();
			status = true;
		} catch(Exception e) {
			status = false;
		}
		return status;
	}
	
	static boolean solve() {
		if(input()) {
			return solve(a, b);
		} return false;
	}
	
	private static boolean solve(long a, long b) {
		if(a == s || b == s) return true; 
		else if(a > s || b > s) return false;
		else {
			long _a = a, _b = b;
			a += _b; 
			b += _a; 
			return solve(a, _b) || solve(_a, b);
		}
	}
	
	public static void main(String[] args) {
		if(solve()) System.out.println("YES");
		else System.out.println("NO");

	}

}

djm03178 3년 전 2

상당한 정수론 지식이 있어야 풀 수 있는 문제라고 합니다. 플래티넘1이나 되는 이유가 그것입니다.

hjj5612 3년 전 0

어떤 책을 참조해야할까요? 책 추천 부탁드릴께요.

djm03178 3년 전 4

저도 못 풀어서 모르겠습니다...

paldad 3년 전 4

안녕하세요.

저도 배우는 입장이지만..

조금 도움이 될까 싶어 몇 가지 조언을 드리고자 합니다.

이 문제는 수의 범위가 10^18 로 몹시 크기 때문에 DP 등 값을 일일히 만들어 보는 방법으로는 풀 수 없고, 정수의 몇 가지 성질을 이용해야 합니다.

(A, B) 로부터 a+=b, b+=a 를 통해 만들어진 수를 (iA+uB, jA+vB) 라고 설정하면,

이들의 합 (i+j)A + (u+v)B 는 A, B 의 정수선형결합이므로,

베주의 정리에 의해 (i+j)A + (u+v)B = Q*gcd(A, B) 가 됨을 알 수 있습니다.

또한 a+=b, b+=a 관계식에 의해 생성된 i, j, u, v 사이에는 iv - ju = 1 or -1 이 성립하므로,

이 또한 식을 잘 정리해보면

iv + jv - jv - ju = 1 or -1

(i+j)v - (v+u)j = 1 or -1

베주의 정리에 의해 i+j 와 v+u 또한 gcd(i+j, u+v) = 1 이 성립한다는 것을 알 수 있습니다.

따라서 이 문제는 (확장) 유클리드 알고리즘을 통해 Ax + By = gcd(A, B) 의 첫 해를 찾은 다음, 일반해들을 순회하면서 다음 조건이 성립하는 해가 존재하는지를 알아보는 것입니다.

* Ax + By = S

* gcd(x, y) = 1

* x > 0, y > 0

위 식은 입력으로 A, B, S 에 0 이 들어오는 경우를 포함하지 않으므로, 이 경우는 특별히 처리해야 합니다.

deuslovelt 3년 전 0

위 댓글에서 구현 시 추가적으로 고려해야 하는 부분이 있는데

수의 범위가 1e18 이기 때문에 오버플로우에 대해 적절히 처리해줘야하고

처음에 a==s || b==s 인 경우 또한 따로 처리해줘야 합니다.

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

문제

문제

출처

ICPC

재귀호출로는 해결을 못하네요. 도움 주세요.

hjj5612 3년 전 0

djm03178 3년 전 2

hjj5612 3년 전 0

djm03178 3년 전 4

paldad 3년 전 4

deuslovelt 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말