알고리즘/백준 알고리즘

[백준 9095] 1, 2, 3 더하기

글에 개요 백준 알고리즘 9095번 "1, 2, 3 더하기" 문제입니다.이 문제는 DP(동적 계획법)을 활용하는 문제로 팰린드롬에 이어 2번째 등장이네요.아마 동적 계획법에 사용되는 점화식의 활용에 익숙해지고, 이후 재귀함수로 구현할 때 Top-down, Bottom-up 방식해 질 때까지 최대한 꾸준히 풀어볼 생각입니다. [백준 9095] 1, 2, 3 더하기: https://www.acmicpc.net/problem/9095 참고할 글[백준 10942] 팰린드롬? : http://brenden.tistory.com/27핵심 내용정수 n을 1,2,3의 조합으로 나타내는 방법의 수를 구하는 문제입니다.D[i] = i를 1,2,3의 조합으로 나타내는 방법의 수D[i] = D[i-1] + D[i-2] + D..

2018. 4. 20. 11:12

알고리즘/백준 알고리즘

[백준 11048] 이동하기 (DP, 최댓값,최솟값 구하는 문제로 확장)

글에 개요 백준 알고리즘 11048번 "이동하기" 문제입니다. DP를 활용하는 기본적인 문제입니다.해당 문제는 이동하면서 주울 수 있는 캔디의 최댓값을 구하는 문제이지만 캔디의 최솟값을 구하는 문제로도 확장해서 해결해 보겠습니다.두 가지 방법으로 해결하겠습니다. 하지만, 핵심은 같습니다!!!최댓값 구하는 방법은 [해결방법1번]으로 구하는게 좋습니다!!최솟값 구하는 방법은 [최솟값 해결방법2번]으로 구하는게 깔끔합니다!! [백준 11048] 이동하기 : https://www.acmicpc.net/problem/11048 핵심 내용시간 초과 이슈를 줄이기 위해 DP를 활용하자!!(1,0), (0,1), (1,1) 방향으로 이동할 수 있지만 점화식을 세울 때 생각해보면, 캔디 숫자는 음수가 될 수 없으므로 (..

2018. 4. 17. 16:39