📚 알고리즘/DP(다이나믹 프로그래밍)
[백준 11057] 오르막수_dp(c++)
1.문제 https://www.acmicpc.net/problem/11057 11057번: 오르막 수 오르막 수는 수의 자리가 오름차순을 이루는 수를 말한다. 이때, 인접한 수가 같아도 오름차순으로 친다. 예를 들어, 2234와 3678, 11119는 오르막 수이지만, 2232, 3676, 91111은 오르막 수가 아니다. 수� www.acmicpc.net 2.접근방법 이것도 처음에 dfs백트래킹인지 dp인지 헷갈렸음(결국 너무 생각해내기 어려워서 다른 사람들 아이디어 살짝 봤다..) 나의 바로 전에 숫자가 무엇이 오는지에 따라 고를 수 있는 수가 달라짐 3.문제풀이 dp[] (행의 인덱스) dp[][] (열의 인덱스 자리수를 표현 0~9까지의 숫자를 표현 n까지의 자리수 중에서 첫번째 자리수는 모든 숫..
[백준 17069] 파이프 옮기기 2(C++)
[문제] https://www.acmicpc.net/problem/17069 17069번: 파이프 옮기기 2 유현이가 새 집으로 이사했다. 새 집의 크기는 N×N의 격자판으로 나타낼 수 있고, 1×1크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 (r, c)로 나타낼 수 있다. 여기서 r은 행의 번호, c는 열의 www.acmicpc.net [접근방법] 1. 처음에 완전탐색(BFS)으로 문제를 풀이하려고 했다... 2. 하지만 메모리 초과의 이유로 풀수 없는 문제라고한다.. 3. 다이나믹프로그래밍을 써서 마지막 n-1,n-1 지점에 저장되어 있는 dp값이 정답! 4. 점화식을 구해 top-down이나 bottom-up 으로 쓰는 방법과는 다르게 3차원 배열을 이용하여 전에 기억하고 있는 값을 계속 더..