강의로 돌아가기
jar100

7번부터 정답이 틀렸다 나오는데 힌트좀 얻을 수 있을까용?

제가 실행 했을땐 문제가 없는거 같은데 어디서 문제가 생겼는지 테스트 코드를 모르니 막혀 답답하네요

  • 혹시 아시는분 힌트좀 주실 수 있나영?

    class Solution {
    public int solution(int n) {
        int[] nums = new int[n+1];
        nums[0] = 0;
        nums[1] = 1;
        nums[2] = 1;
    
        for (int i = 3; i <= n; i++) {
            nums[i] = nums[i-1] + nums[i-2];
        }
    
        return nums[n] % 1234567;
    }
    }
    

문제가 잘못된거 같습니다. 조건은 마지막 n 번째에 1234567 을 나눈 값을 리턴하라고 그러는데

for 문 안에 1234567 을 나누고 nums[n]을 리턴시키니 통과 되네요
제가 조건을 잘못 이해한것인지 문제가 잘못된건지 알려 주실 수 있나요?

for (int i = 3; i <= n; i++) {
            nums[i] = (nums[i-1] + nums[i-2]) % 1234567;
        }
2 개의 답변
Vanary

조건도 잘 이해하셨고 문제도 옳은 것 같습니다.

F(N) % 1234567 = ( F(N-1) % 1234567 + F(N-2) % 1234567 ) % 1234567 이게 성립하네요.

  • jar100
    result 값이 피보나치(n) 에 1234567 의 나머지 값 아닌가용? 아래 질문드린 코드로 하면 nums[i-1] num[i-2] 값에도 %1234567 값이 들어가 값이 줄어드는뎅.... jar100 2018.10.10 14:59
  • jar100
    위에 질문드린 피보나치를 다 구하고 result 에서 나누는 코드로 짜면 왜 안되는건지 알 수 있을까요??.... jar100 2018.10.10 15:08
  • 김성렬
    아 그러네요! 감사합니다. 김성렬 2018.10.22 14:15
  • kyounghwan Noh
    위 안되는 코드로 n 값을 12345678 이상을 주니까 infinity로 나오네요 감당하는 수 단위 이상으로 올라가서 오류처리시킨 것 같아요 kyounghwan Noh 2019.04.09 18:28
박성열

n번째 피보나치 수를 1234567으로 나눈 나머지를 리턴 이라는 의미가,
아마도 F(N) % 1234567 = F(N - 1) % 1234567 + F(N - 2) % 1234567 인 공식을 성립시킨 값을 리턴하라는 의미인 것 같습니다.
제가 수학을 잘 못해서 정답인지는 모르겠지만..
저도 7번부터 테스트케이스가 틀렸다고 떠서 정답인 코드와 제가 작성한 코드를 비교해보니
질문자분처럼 마지막 값에 1234567 로 나눈 나머지만을 리턴하고 있었습니다
즉, F(N) = F(N - 1) + F(N - 2) 에 대한 수열 값을 구해놓고,
return F(N) % 1234567 ; 만 하였습니다.

제 생각에는 테스트케이스 1~6 에서의 답이 1234567 보다 작은 수여서 정답이 나왔지만
7번부터는 테스트케이스의 답이 1234567 보다 커서 통과되지 않은 것으로 보입니다

답변 쓰기
이 입력폼은 마크다운 문법을 지원합니다. 마크다운 가이드 를 참고하세요.