Comments (8)
손으로 하나씩 다 써보니까 제가 했던 방법은 말씀하신대로 사자가 아예 없을 경우는 뺀 경우의 수를 구하게 되네요
저는 마지막 +1 해주는 것이 사자가 없을 경우를 생각해서 더해준 것인데, 이 말은 즉, 전체에 사자가 없을 경우이지, 행마다 사자가 없는 경우를 더해준 적이 없는 것 같습니다. 그래서 +1한게 우연이 맞은 것 같네요,,
구글링과 다른 풀이법을 생각한 줄 알고 계속 붙잡고 있었는데 아니었군요,,, 도대체 dp는 감이 안잡히네요!!!!
읽어주셔서 감사합니다!! 해결됐어용 ㅎㅎ
ps. 혹시 선생님 강의 하시는 것이나 질문에 답해주신 풀이들 정리해서 블로그에 올려도 되나요,,, 출처는 깃헙주소로 밝히겠습니다. 예를 들어, 그래프 단원을 듣고 인접행렬, 인접리스트가 있고, 거기에 시간복잡도와 장단점, bfs는 언제 사용하는 지 등 pdf 그대로가 아닌 제 말로 해석해서 쓰고싶은데 혹시 가능할까요??
from fastcampus.
안녕하세요. 저도 동물원 알고리즘으로 오늘 2시간 정도를 소요했는데요,
제가 비교적 간단한 점화식을 찾아내서 댓글 남깁니다.
기존에 강사님께서 도출하셨던 간단한 방법인데요,
n =1 일 때는 사자가 없거나, 왼쪽에 있거나 오른쪽이 있거나 해서 n =1 경우의 수가 3
입니다.
n = 2 일 때는 n =2 경우의 수 7
입니다.
n = 3 일 때는 n =2 경우의 수 17
입니다.
그리고 문제에서 n =4 경우의 수 41
을 주었으니 이 4개의 상관 관계를 따져보면
n 이 3 일때 dp[n-2] + (dp[n+1]*2)
를 하게되면 3+ (7*2) = 17
이 됩니다.
이 식을 참고해서 푸니
private static void pro() {
dp[1] = 3 % 9901;
if(N>2) {
dp[2] = 7 % 9901;
}
for (int i = 3; i <= N; i++) {
dp[i] = (dp[i - 2] + (dp[i - 1] * 2)) % 9901;
}
System.out.println(dp[N] % 9901);
}
이렇게 하면 풀리더군요. if 문을 걸어놓은 이유는, 만약 N = 1 일 경우에 오버플로우가 나서 방지하기 위함입니다!
제 코드도 참고해서 생각해주시면 감사하겠습니다 ㅎㅎ
그럼 즐거운 코딩 하세요 :)
from fastcampus.
dp[i][j] 의 정의가 어떻게 되시나요?
from fastcampus.
i 번째 줄 , j칸에 사자가 들어갈 수 있는 경우의 수입니다.
from fastcampus.
계속 생각해봤는데 제가 말씀드린 dp 정의가 말이 이상한 것 같습니다,,
규칙이 눈에 보였는데 문제가 풀리지 않아서 계속 붙잡고 있었던 것 같기도 합니다,,
값을 구할 때, i = N일 때, 답이 나와야하는데 애초에 잘못 생각했던 것 같습니다,,
from fastcampus.
말씀하신 방법으로 하면 적어주신 방법이 정답이 맞습니다. 올바르게 생각하신 거 맞아요!
다만 말씀하신 것처럼 i 가 커질수록 더해야 하는 게 많아지죠? 그 이유는 "i-1 번 줄에 사자가 한 마리도 없는 경우" 를 dp[i-1][0] 이나 dp[i-1][1] 로는 절대로 알 수 없기 때문입니다. 왜냐하면 dp[i-1][0]이나 [1] 모두 사자가 무조건 존재해야 하기 때문이죠.
저같은 경우는 j=2 인 경우를 새로 만들 것 같습니다.
dp[i][0] = 1번~i번 행에 사자를 올바르게 나열하는 방법들 중에서, i 번행 0 번 열에 사자가 있는 경우
dp[i][1] = 1번~i번 행에 사자를 올바르게 나열하는 방법들 중에서, i 번행 1 번 열에 사자가 있는 경우
dp[i][2] = 1번~i번 행에 사자를 올바르게 나열하는 방법들 중에서, i 번행에 사자가 전혀 없는 경우
이렇게 만들면 아마 고민하셨던 "식이 너무 길다" 가 해결되실 것 같아요.
from fastcampus.
넵 상관없습니다!
from fastcampus.
@her0807
이차원 배열 이용한 풀이는 직관적이어서 쉬운데
일차원 배열이 생각하기 어렵군요
코드 공유 감사드립니다.
from fastcampus.
Related Issues (20)
- 호석 사우르스 HOT 1
- 다익스트라 관련 질문 HOT 1
- 호석사우르스 python 해설 코드가 누락되어있습니다
- 골목대장 호석 HOT 1
- FastCampus/류호석배 알고리즘 코딩 테스트/제1회/4번-꿈틀꿈틀 호석 애벌레/python 해설 HOT 2
- 14502 연구소 해설코드 질문이 있어서 깃헙에 질문 같이 적어놓았습니다. HOT 2
- 1182 부분수열의 합 질문입니다. HOT 2
- 안녕하세요 입력 받는 과정에 질문이 있어 드립니다. HOT 1
- 전역변수 사용 HOT 1
- [Part.5 / Ch 02 / 01. 어떻게든 푼다. 완전 탐색 (Brute Force) - 응용편 / 09 : 06] HOT 1
- [Part.2 / Ch 03 / 01. 재귀 함수 이론 / 29 : 12] HOT 1
- 투포인터 연습문제 - 2473 세 용액 파이썬 HOT 1
- 강의외로 류호석강사님과 소통할 채널은 없는걸까요?!! HOT 1
- 15970(화살표 그리기) 질문 드립니다.
- 골목 대장 호석 HOT 1
- 골목대장호석V2 HOT 1
- 호석이두마리치킨 HOT 1
- 광부호석 HOT 1
- c++ 답안에서 배열들 선언하실때 크기 HOT 2
- 짠돌이 호석 HOT 1
Recommend Projects
-
React
A declarative, efficient, and flexible JavaScript library for building user interfaces.
-
Vue.js
🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
-
Typescript
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
-
TensorFlow
An Open Source Machine Learning Framework for Everyone
-
Django
The Web framework for perfectionists with deadlines.
-
Laravel
A PHP framework for web artisans
-
D3
Bring data to life with SVG, Canvas and HTML. 📊📈🎉
-
Recommend Topics
-
javascript
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
-
web
Some thing interesting about web. New door for the world.
-
server
A server is a program made to process requests and deliver data to clients.
-
Machine learning
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
-
Visualization
Some thing interesting about visualization, use data art
-
Game
Some thing interesting about game, make everyone happy.
Recommend Org
-
Facebook
We are working to build community through open source technology. NB: members must have two-factor auth.
-
Microsoft
Open source projects and samples from Microsoft.
-
Google
Google ❤️ Open Source for everyone.
-
Alibaba
Alibaba Open Source for everyone
-
D3
Data-Driven Documents codes.
-
Tencent
China tencent open source team.
from fastcampus.