늘 겸손하게

목차 문제명 문제풀이 코드 백준 1890 점프 문제 유형 : 다이나믹 프로그래밍 (DP, Dynamic Programming ) 난이도 : 실버 1 https://www.acmicpc.net/problem/1890 13904번: 과제 예제에서 다섯 번째, 네 번째, 두 번째, 첫 번째, 일곱 번째 과제 순으로 수행하고, 세 번째, 여섯 번째 과제를 포기하면 185점을 얻을 수 있다. www.acmicpc.net 문제 N×N 게임판에 수가 적혀져 있다. 이 게임의 목표는 가장 왼쪽 위 칸에서 가장 오른쪽 아래 칸으로 규칙에 맞게 점프를 해서 가는 것이다. 각 칸에 적혀있는 수는 현재 칸에서 갈 수 있는 거리를 의미한다. 반드시 오른쪽이나 아래쪽으로만 이동해야 한다. 0은 더 이상 진행을 막는 종착점이며, ..

made by : besforyou 문제풀이 n을 입력받고, n을 1, 2, 3의 합으로 나타내는 모든 경우를 구할 필요없이 과거 기록을 이용하는 dp 알고리즘을 이용하여 해결하면 편리합니다. - n이 1인 경우 1, 2, 3의 합으로 나타내는 방법 1 : 1가지 - n이 2인 경우 1, 2, 3의 합으로 나타내는 방법 1 1 2 : 2가지 - n이 3인 경우 1, 2, 3의 합으로 나타내는 방법 1 1 1 1 2 2 1 3 : 4가지 - n이 4인 경우 1, 2, 3의 합으로 나타내는 방법 1 1 1 1 1 2 1 2 1 1 3 1 1 1 2 2 2 1 3 : 7가지 n이 4인 경우를 보면 3을 1, 2, 3의 합으로 나타낸 모든 경우 + 1 2을 1, 2, 3의 합으로 나타낸 모든 경우 + 2 1을 ..

wrote by : besforyou 문제 해설 n이 주어지고, 위 피보나치 함수를 실행했을때 0과 1이 반환되는 횟수를 출력하는 문제입니다. 단순히 위 함수를 실행해서 반환되는 0과 1의 횟수를 직접 구하는 알고리즘은 시간 초과가 뜹니다. 그래서 dp를 적용하여 문제를 해결해야합니다. 문제풀이 fibonacci(0)은 0을 1번, 1을 0번 반환하고 ---- (a) fibonacci(1)은 0을 0번, 1을 1번 반환합니다. ---- (b) fibonacci(2)는 fibonacci(1) + fibonacci(0)을 반환합니다. 그러므로 0을 1번, 1을 1번 반환합니다. ( a + b ) 위를 통해서, n이 주어졌을때 0과 1이 반환되는 횟수는 함수에 n-1이 주어졌을때 반환한 0과 1의 개수와 함수..

안녕하세요 besforyou입니다 백준 문제 10709번 문제 풀이를 설명하겠습니다 문제 풀이 c가 나온 지점으로부터 오른쪽으로 얼마나 떨어져 있는지를 알아내어 출력하는 문제입니다. 이 문제에 dp 알고리즘을 적용하면 O(H*W) 시간안에 풀어낼 수 있습니다. 1. 구름의 위치 입력값을 받을 2차원 배열 cloud와 정답을 기록할 2차원 배열 ans를 생성합니다. 2. 2차원 배열 ans의 모든 원소값은 -1로 초기화합니다. (memset 이용) 3. 2차원 배열 cloud에 모든 입력값을 저장합니다. 4. for문을 이용하여 cloud의 모든 원소를 순차적으로 참조하는데, 1. 해당 cloud 좌표에 c가 있는 경우 : 0 2. c가 참조되지 않았지만 이전 원소가 -1이 아닌 경우(c가 이전에 이미 읽..