링크: https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWqPrpnKSCQDFAT_문제경로에서 등장하는 모든 숫자의 곱에서 맨 뒷자리에 연속으로 있는 0의 개수, 즉 trailing zero의 개수의 최소를 구하는 문제입니다.trailing zero가 나오기는 위해서는 10의 배수라는 의미이고, 소인수 중 2와 5의 개수 중 작은 쪽만 확인하면 됩니다.이 부분은 BOJ 1676 - 팩토리얼 0의 개수 문제에서 풀어보시면 됩니다.가장 왼쪽 위 (1, 1) 지점에서 시작해서 오른쪽 또는 아래쪽으로만 이동한다는 점은,다음 지점의 입장에서는 위쪽 또는 왼쪽의 영향만 받는다는 의미이기도 하지요.항상 위쪽 또는 왼쪽까지 도착..

링크: https://www.acmicpc.net/problem/5535문제각 날짜마다 입을 수 있는 옷들이 있고, 다음 날과 옷의 화려함의 차이가 최대한 크도록 옷을 고르는 문제이다.날짜마다 가능한 옷을 저장해둔다. 그 날에 한해서는 옷의 종류나 순서가 중요치않길래 화려함 정도를 넣어버렸다. 이제 각 날짜마다 옷을 하나씩 고른다면, 총 D일동안 N가지의 옷을 고르므로 경우의 수는 \(O(N^{D})\) 이다. 어떤 d번째 날에 A라는 옷을 골랐다고 치자. 그럼 d+1번째 날 이후로는 d번째 날에 A를 고른 영향이 계속 생긴다.즉, d번째 날에 a를 고른 이후로는 하나의 부분 문제로 볼 수 있다. 점화식을 dp[D][N] = D번째 날에 N번째 옷을 선택했을 때의 화려함의 최대값 으로 세우면 \(O(ND..

링크: https://www.acmicpc.net/problem/17521문제보자마자 주식 문제가 생각났다.주식 문제들은 최대 이익을 내기 위해서 그리디하게 행동하면 된다. 값쌀 때 사서 값비쌀 때 팔면 된다.이 문제에서는 늘어난 코인만큼 다시 투자를 할 수 있으니, 상승 곡선이면 무조건 사는것이 이득이다. (늘어난 코인을 배로 불릴 수 있으니)코드 직관적으로 풀었지만 내심 불안했다.그래서 dp로도 풀어보았다. 물론, 같은 결과가 나왔고 정답이다.점화식은 dp[k] := k일까지 벌 수 있는 최대 코인이다.\(i < j\) 인 \(i\)일째에 가진 돈으로 전부 매수하고, \(j\)일에 모두 매도한다면 (두 날짜 사이의 변폭) * (i일에 살 수 있었던 코인의 수)만큼 벌 수 있을것이다.

링크 1: https://uva.onlinejudge.org/...problem=1859 링크 2: BOJ 2133 - 타일채우기(https://www.acmicpc.net/problem/2133) 문제 타일 시리즈 중에 하나로, 3×N 크기의 벽을 2×1, 1×2 크기의 타일로 채우는 문제이다. 풀이 3×n 크기의 벽을 채우는 경우의 수를 \(f(n)\)이라고 하자. 다음은 전개될 수 있는 모든 모양이다. 모양이 반복되는 경우까지만 적었다. .... x... .... f(n) = .... g(n) = .... or .... .... .... x... A..... AA.... A..... or ...... ...... ...... A..... ACC... ACC... ACC... A..... -> A....

링크: https://www.acmicpc.net/problem/14852 문제 타일 시리즈 중 하나인데, 2×N 크기의 벽을 2×1, 1×2, 1×1 크기의 타일로 채우는 경우의 수를 구하는 문제이다. 먼저 왼쪽부터 타일을 채워가면서 생기는 모양에 따라 부분 문제를 만들어나간다. 아래와 같은 모양을 각각 \(f(n), g(n)\)이라고 정의해보자. \(g(n)\)은 첫 번째 열 중에서 한 칸만 채워진 경우이다. 두 모양이 채워질 수 있는 Base case를 이렇게 정의하자. \(f(0)\)은 모든 타일을 채웠다는 뜻으로 1개로 센다. \(g(0)\)은 불가능한 모양이므로 0이다. 먼저 \(g(n)\)은 아래와 같이 세 가지 모양으로 전개될 수 있다. 첫 번째 열의 빈칸에 1×1짜리 타일을 하나 채우면 ..

링크: https://www.acmicpc.net/problem/2096문제어떤 칸을 선택하면 선택 가능한 다음 칸이 정해지는 점에서 9465번 - 스티커와 굉장히 유사합니다. 사실 동일한 풀이로 해결되지만 다른 점이 있습니다.이 문제는 메모리의 제한이 4MB로 엄청 작다는 겁니다.적은 메모리 제한때문에 스티커 문제처럼 dp[3][N] 과 같은 배열을 선언할 수도 없고 재귀 함수까지도 염려해야하는 상황입니다. 그럼 어떻게 해결해야할까요?풀이어떤 r번째 줄에서 어떤 칸을 선택한다면, 이는 다음 줄인 r+1번째 줄에 영향이 갑니다. 어떤 칸을 선택할 때, 항상 2개의 줄만 확인하면 된다는 점으로 메모리를 줄일 수 있습니다. 왜냐하면 1번째 줄은 2번째 줄에 영향을 주고 2번째 줄은 3번째 줄에 영향을 주지만..

링크: https://www.acmicpc.net/problem/9465예전 풀이: http://joonas-yoon.blogspot.com/2014/08/9465.html풀이한 스티커(칸)를 선택하면 인접한 칸은 선택할 수 없게 된다.그럼 대각선만 남게 되는데, 그 대각선 칸도 위 선택을 반복하게 된다. A B C DE F G H 만약 위와 같이 있다고 생각해보자. A를 고른다면 C, D, F, G, H 중에 골라야한다. E를 고른다면 B, C, D, G, H 중에 골라야한다.바로 다음 칸(열)에만 영향이 있고, 그 이후의 C, D, G, H를 고민하는 것은 변함이 없다. 즉 어떤 i번째 열을 볼때, i+2번째 이후의 열은 영향이 없다는 뜻이다. i번째 열에서 고민할 점은 3가지이다. 1. 고르지 않는..

링크: https://www.acmicpc.net/problem/11058출력 결과에 영향을 미치는 연산이 A를 그냥 누르는 거랑(+1), Ctrl-V (+복사했던 크기) 인데 클립보드에 복사해놓은 크기때문에 재귀로 짜는데 애를 먹었다. 복사한 크기만큼 늘어나기 때문에, Ctrl-V 를 하기 위해서는 이전에 Ctrl-A, Ctrl-C 가 꼭 필요하다. 문제에 적힌 연산을 순서대로 A, S, C, V 라고 한다면 \(N=6\)인 경우는 아래와 같이 가능하다. AAAAAAAAASCVAASCVVASCVVV 이 정도가 의미있는 타이핑인거같다. 타이핑을 \(n\)번한 것을 \(f(n)\)이라 하자. 그럼 위 4줄은 각각 \(f(5)+1\), \(f(3)∗2\), \(f(2)∗3\), \(f(1)∗4\) 이다. $..