밍맹의 생각날 때 적는 블로그

[문제 링크] 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net 사용자에게 입력받은 수를 다음과 같은 조건으로 1로 만드는 최소 경우의 수를 찾으면 된다. 1을 뺀다 2로 나누어진다면 2로 나눈다. 3으로 나누어진다면 3으로 나눈다. 10을 예시로 들면 10 -> 9 -> 3 -> 1로 총 3번이면 1로 만들 수 있다. 이 문제는 다이내믹 프로그래밍(DP)으로 풀 수 있다. 다이내믹 프로그래밍이란 큰 문제를 작은 문제로 단순화시켜 해결하는 알고리즘이다. 10에서 1을 뺐을 경우 9가 된다. 여기서 우리가 만약 9가 1이 되는 최소 횟수를 알고 있다면?? (9가 1이 되는 최소 횟수) + 1 (10에서 1을 빼 9로 갈 때 횟..

문제 오른쪽 그림과 같은 핸드폰 자판이 있다. 이 자판을 이용하여 어떤 영어 메시지를 치려고 할 때, 걸리는 최소 시간을 구하는 프로그램을 작성하시오. 단, 1번은 누를 경우에는 공백이 찍힌다고 하자. 그리고 만약에 AC라는 문자를 치려 한다면 A를 치고 난 후 일정 시간을 기다린 후 C를 치면 된다. 하나의 문자를 입력하려면, 버튼을 눌러야 한다. 버튼을 누르면 버튼에 쓰여 있는 문자가 입력되며, 버튼을 누를 때마다 다음 문자로 바뀌게 된다. 예를 들어, 2를 누르면 A, 2번 누르면 B, 3번 누르면 C이다. 공백을 연속으로 누를 때는 기다릴 필요가 없다. 입력 첫째 줄에 p와 w가 주어진다. (1 ≤ p, w ≤ 1,000) p는 버튼을 한번 누르는데 걸리는 시간이고, w는 AC와 같은, 같은 숫자..