동적프로그래밍 썸네일형 리스트형 백준 알고리즘 2579번 이 문제는 각 단계마다 경우의 수가 몇가지 존재하고 그 중 가장 큰 값만을 저장하고 단계를 진행하는다이나믹 프로그래밍문제이다. 하지만 몇가지 제약이 존재하는 DP라고 볼 수 있다. 조건을 회피하고 생각하는 것보다 조건을 처음부터 생각하며 DP 점화식을 세우는 것이 적절하다.DP문제는 이 점화식을 세우는 것이 관건인데, 뒤에서부터 고려하여 식을 짜는 것이 수월하다. 제약 조건을 살펴보면한번에 1칸 또는 2칸을 오를 수 있다.연속 3칸을 밟은 순 없다.마지막 계단은 반드시 밟아야 한다. 뒤에서부터 생각하면, 마지막 계단은 반드시 밟아야하고 연속적으로 3칸은 밟을 수 없으므로나올 수 있는 경우의 수는 2가지이다.전 단계의 계단을 밟는 경우전 단계의 계단을 밟지 않는 경우 즉, 위와 같은 경우의 수 2가지를 점.. 더보기 백준 알고리즘 1149번 마찬가지로 문제를 풀기 전에 어떠한 알고리즘을 써야할지 생각을 해보자.각 단계마다 경우의 수가 존재하고 그 경우의 수 중에 가장 최소값을 구하는 문제이다. 사용해야할 기법은 다이나믹 프로그래밍 ! 단순하게 생각하자면 점화식은 [n - 1]의 최소값 + [n]의 최소값이다.전 단계의 최소값과 지금 단계의 r,g,b 중 가장 작은 값을 더하는 것이다. 하지만 여기서 하나 더 생각해야되는 조건이 있다.바로 전 단계의 r,g,b와 겹치면 안된다는 것이다. 내가 만약 r을 선택했다면 그 전 단계는 b, g중 최소 값을 더해야 된다는 뜻이다. 이 조건을 생각해서 다시 점화식을 세우면min = Min([n - 1][g] + [n - 1][b]) + r 이 된다. r,g,b 선택한 3가지 경우의 수중 제일 작은 값 하.. 더보기 백준 알고리즘 1463번 1로 만들기 성공 풀이문제집 시간 제한메모리 제한제출정답맞은 사람정답 비율2 초128 MB306589750653433.225%문제정수 X에 사용할 수 있는 연산은 다음과 같이 세 가지 이다.X가 3으로 나누어 떨어지면, 3으로 나눈다.X가 2로 나누어 떨어지면, 2로 나눈다.1을 뺀다.정수 N이 주어졌을 때, 위와 같은 연산 세 개를 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의 최소값을 출력하시오.입력첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 자연수 N이 주어진다.출력첫째 줄에 연산을 하는 횟수의 최소값을 출력한다.예제 입력 복사2 예제 출력 복사1 예제 입력 2 복사10 예제 출력 2 복사3 힌트10의 경우에 10 -> 9 -> 3 -> 1 로 3번 만에 만들 수 있다. #.. 더보기 이전 1 다음
