문제를 2가지 방법으로 풀었다.
첫 번째 방법은 노트를 없이 풀었는데, 문제를 잘 못 이해해서 시간초과가 났고,
두 번째 풀이는 메모이제이션을 이용해 코드를 작성했다.
Dynamic-Programming
BOJ 2951 풀이 (Olympiad > 한국정보올림피아드시․도지역본선 > 지역본선 2005 > 초등부 5번 Olympiad > 한국정보올림피아드시․도지역본선 > 지역본선 2005 > 중등부 3번)
2017. 10. 25. 20:28
BOJ 12852 1로 만들기 2 풀이
2017. 10. 20. 15:55
음..
DP로 풀었다. 계단문제랑 비슷하다.
처음에는 그냥 3나눠지면 3하고 2되면 2하고 했는데, 그게 아니라 경우의수가 최소일 때 를 구하는것 이였다.
그래서 메모이제이션이랑 Stack을 이용해서 경로구하는거 까지 구현했다.
'IT > 알고리즘' 카테고리의 다른 글
| BOJ 2042 구간 합 구하기 풀이 (0) | 2017.10.24 |
|---|---|
| BOJ 2589 풀이 (Olympiad > 한국정보올림피아드시․도지역본선 > 지역본선 2005 > 초등부 3번) (0) | 2017.10.23 |
| 2611 자동차경주 풀이 (Olympiad > 한국정보올림피아드시․도지역본선 > 지역본선 2004 > 중등부 5번) (0) | 2017.10.20 |
| BOJ 2016 풀이 2004 (한국정보올림피아드시․도지역본선) (0) | 2017.10.19 |
| BOJ 11657 타임머신 풀이 벨만 포드 (0) | 2017.10.19 |
BOJ 14852 타일채우기 3 풀이
2017. 10. 18. 23:08
와.. 문제를 푸는데 2시간이 걸렸다.
코드에 변화가 2번이 일어났는데, 처음에는 subproblem을 너무 쉽게 생각했고,
그 다음에는 반복문 내용을 수정했다..
풀이 방법은
위에 1x2랑 1x1로 채우고 밑에를 n-1로 해줘서 d[n-1] * 2
그리고 2x1, 1x1로 채우고 밑에를 n-2로 채워서 d[n-2] * 3
그리고 1x2, 2x1, 1x1을 전부 사용해 위에를 채운건 d2[n-1]+d[n-3] * 2
합치면 d[n-1]*2+d[n-2]*3+(d2[n-1]+d[n-3])*2
'IT > 알고리즘' 카테고리의 다른 글
| BOJ 2016 풀이 2004 (한국정보올림피아드시․도지역본선) (0) | 2017.10.19 |
|---|---|
| BOJ 11657 타임머신 풀이 벨만 포드 (0) | 2017.10.19 |
| BOJ 2309 일곱난쟁이 풀이 (0) | 2017.10.18 |
| BOJ 2065 줄 세우기 (0) | 2017.10.18 |
| BOJ 11404 플로이드 Floyd-Warshall (0) | 2017.10.18 |