(C++) - 프로그래머스(연습문제) : 멀리 뛰기
https://programmers.co.kr/learn/courses/30/lessons/12914 코딩테스트 연습 - 멀리 뛰기 효진이는 멀리 뛰기를 연습하고 있습니다. 효진이는 한번에 1칸, 또는 2칸을 뛸 수 있습니다. 칸이 총 4개 있을 때, 효진이는 (1칸, 1칸, 1칸, 1칸) (1칸, 2칸, 1칸) (1칸, 1칸, 2칸) (2칸, 1칸, 1칸) (2칸, 2 programmers.co.kr dp문제였습니다. 풀이방법 1칸 또는 2칸을 뛰므로 n에 도착하기 위한 경우의 수 점화식은 다음과 같습니다. D[n] = D[n-1] + D[n-2] Code #include #define MOD 1234567 using namespace std; using ll = long long; ll d[2001]..
(C++) - 백준(BOJ) 2096번 : 내려가기
www.acmicpc.net/problem/2096 2096번: 내려가기 첫째 줄에 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 숫자가 세 개씩 주어진다. 숫자는 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 중의 하나가 된다. www.acmicpc.net dp문제였습니다. 풀이방법 메모리 제한이 4mb이므로 400만 byte크기 이하의 변수들을 선언해 사용해야 합니다. 이 문제는 10만개의 배열 이상 사용하지 않아도 되는 문제입니다. 1. 첫 번쨰 행의 세 수를 먼저 입력 받습니다. 그 후 d, d2배열에 각각 저장합니다. 2. 현재 열이 0번째 열이면 이전의 행에서는 0,1번째 열 중 최대값에서 현재 열의 값을 더한값이 현재 열이 가질 수 있는 최댓값입니다. 현재 열이 1번..
(C++) - 백준(BOJ) 15988번 : 1, 2, 3 더하기 3
www.acmicpc.net/problem/15988 15988번: 1, 2, 3 더하기 3 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 1,000,000,009로 나눈 나머지를 출력한다. www.acmicpc.net dp문제였습니다. 풀이방법 * 답이 나올 수 있는 범위를 조심해야합니다. int범위를 초과할 수 있으므로 long long으로 변수를 선언해줘야합니다. * 테스트 케이스로 인해 출력이 많아지므로 c와 동기화를 끊어 입출력이 빨라지도록 합니다. * Modular 연산을 주의해야합니다. 덧셈에 대해 분배법칙이 성립하나 더할 때 마다 범위가 초과할 수 있으므로 매번 더할 때 마다 Modular 연산을 해줘야 합니다. i를 만드는 경우의 수는 i-1을 만드는 경우의 수..
