반응형
문제는 다음과 같습니다.
https://school.programmers.co.kr/learn/courses/30/lessons/12914
프로그래머스
코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.
programmers.co.kr
풀이 코드는 다음과 같습니다.
#include <string>
#include <vector>
using namespace std;
long long solution(int n) {
long long answer = 0;
long arr[2001];
arr[0]=0;
arr[1]=1;
arr[2]=2;
for(int i{3};i<2001;i++)
{
arr[i]=(arr[i-1]+arr[i-2])%1234567;
}
answer=arr[n];
return answer;
}
전형적인 피보나치수열 문제입니다.
그 이유는 맨 마지막 n번째 계단을 오르기 위해서는 경우의 수가 2개 존재하는데 그 경우가
n-2번째 계단에서 올라오는 방법과 n-1번째 계단에서 올라오는 방법이기 때문입니다. (계단은 1칸 또는 2칸만 오를 수 있기 때문입니다.)
예시로, 3번째 칸에 올라가기 위해서는 1번째 칸에서 2칸을 오르는(1+1 또는 2) 방법과 2번째 칸에서 1칸을 오르는 방법만 존재하기 때문입니다.
그냥 이렇게 풀면 틀리게 되는데 그 이유는
1234567을 나눈 나머지를 리턴해야하기 때문입니다.
이 부분을 읽지 않고 풀었다가 저 역시 계속 뜨는 오답에 "왜 틀린 거지?" 했습니다. 문제를 끝까지 읽어야 한다는 중요성을 다시 한번 보여준 것 같습니다.
반응형
'프로그래머스 Lv.2 코딩테스트' 카테고리의 다른 글
[프로그래머스 Lv.2] 땅따먹기 (2) | 2022.09.22 |
---|---|
[프로그래머스 Lv.2] 카펫 (2) | 2022.09.21 |
[프로그래머스 Lv.2] 숫자의 표현 (2) | 2022.09.20 |
[프로그래머스 Lv.2] 이진 변환 반복하기 (0) | 2022.09.20 |
[프로그래머스 Lv.2] 올바른 괄호 (0) | 2022.09.08 |