반갑습니다!

10164번: 격자상의 경로 www.acmicpc.net 풀이 등굣길문제와 유사하게 해결하였다. 출발지에서 꼭 들려야하는 지점까지 가는 방법의 수와 꼭 들려야하는 곳에서 N X M 번재 지점까지 가는 방법의 수를 구해서 곱해주면 모든 경로의 개수가 된다. 코드 C++ #include #include using namespace std; int n, m, k, r, c; vector dp1, dp2; int main() { cin >> n >> m >> k; dp1 = vector(n, vector(m, 1)); dp2 = vector(n, vector(m, 1)); if (k == 0) { r = n - 1; c = m - 1; } else { if (k % m == 0) r = k / m - 1; el..

9507번: Generations of Tribbles www.acmicpc.net 풀이 일반적인 피보나치 수열 문제를 풀 듯이 동적 계획법을 사용하면 쉽게 해결할 수 있다. 이 때 최대값이 int 범위를 벗어나기 때문에 long long으로 선언해야 해결할 수 있다. 코드 #include #include using namespace std; vector fib; long long fibonacci(int n) { long long& ret = fib[n]; if (ret != -1) return ret; if (n < 2) return ret = 1; if (n == 2) return ret = 2; if (n == 3) return ret = 4; else return ret = fibonacci(n..

17213번: 과일 서리 www.acmicpc.net 풀이 중복 조합을 사용해서 해결하면 된다. 이 때 중요한 것은 모든 과일의 종류가 최소한 1개는 포함되어야한다는 점이다. 이를 조심해서 구현하면 된다. 조합을 구현할 때는 동적 계획법을 사용해서 구현했다. 코드 #include using namespace std; int n, m; int comb[41][41]; int combination(int a, int b) { int& ret = comb[a][b]; if (ret != -1) return ret; if (b == 0 || a == b) return ret = 1; return ret = combination(a - 1, b - 1) + combination(a - 1, b); } int ma..

15486번: 퇴사 2 www.acmicpc.net 풀이 동적 계획법으로 해결해야하는 문제이다. 동적계획법을 위한 배열을 dp[i]라고 했을 때 dp[i]는 i일 까지 받을 수 있는 최대 금액이라고 정해서 해결하였다. 코드 #include #include using namespace std; int n; int t[1500001], m[1500001]; int dp[1500002]; int main() { ios_base::sync_with_stdio(0); cin.tie(0); cin >> n; for (int i = 1; i > t[i] >> m[i]; int ans = 0; for (int i = 1; i n + 1) continue; dp[i + t[i]] = max(dp[i + t[i]], an..

프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이 동적계획법 문제이다. 이 문제는 수학 시간에 경로의 갯수 문제를 풀던 방식으로 해결하였다. 예시로 살펴보자. S가 출발지점, T가 도착지점이라고 하였을 때 도착지까지 가는 경로의 수는 다음과 같이 구할 수 있다. 출발지점에서 오른쪽으로 이동하거나 아래로 이동하는 방법은 1가지밖에 없기 때문에 값을 1로 갱신해준다. 노란 지점으로 가는 방법의 수를 (2, 2) 라고 하면 (1, 2) 와 (2, 1) 에서 이동할 수 있기 때문에 (1, 2) + (2, 1)가 된다. 위와 같은 방식으로 값을 갱신하면 목적지에..