https://programmers.co.kr/learn/courses/30/lessons/12914?language=cpp
사실 이 문제가 피보나치 수열의 규칙이 있어서 피보나치로 풀어도 됨.
근데 오랜만에 보니까 완전 탐색으로 될 거 같은 거양.
매 선택마다 1을 고를지, 2를 고를지 모든 경우의 수를 다 해보는 거지.
그래서 매 선택을 sum에 누적시켜서 sum이 n과 같아지면 경우의 수 하나 추가!
만약 sum이 n을 넘어가면 그건 실패니까 return 0 했음.
근데 채점해보니까 시간초과랑 예외가 좀 있더라공...
시간 초과가 나는 건 이해를 함.
왜냐면 얘는 메모이제이션을 적용할 수가 없음.
sum의 값으로만 메모제이션을 하면
지난 선택에서 1,1,2 이렇게 골랐는지
1,2,1 이렇게 골랐는지 상관없이 합으로 메모이제이션 하니까 값이 더 적어짐.
그래서 시간초과가 날 거라 생각함
근데 예외는 왜 나는 거지? 모든 경우의 수를 다 돌리는 건뎅;
1,2,3더하기
풀어보자
나머지 계산 ㅇㄷ
아 ㅋㅋㅋㅋㅋㅋ 감사감사
메모이를 왜못해 - dc App
어 되네?? 만약에 n이 4라고 가정할 때 1-1-2랑 1-2-1 다르게 세야 되는 거 아님?
아 아니구나. 이전 합이 뭐가 됐든 간에 다음 부터 조합할 애들이 중요한 거니까 메모이가 되는 게 맞넹
그게 sum - 1, sum - 2잔아 - dc App
ㅇㅇ 이전에 조합했던 애들을 또 호출해서 부르고 있으니까 메모이가 되는 게 맞넹
사이트 신기하네 백준은왜 저런거 안해주냐 메인같은거