Carrot Farming

# 문제 정수 X에 사용할 수 있는 연산은 다음과 같이 세 가지 이다. X가 3으로 나누어 떨어지면, 3으로 나눈다. X가 2로 나누어 떨어지면, 2로 나눈다. 1을 뺀다. 정수 N이 주어졌을 때, 위와 같은 연산 세 개를 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의 최솟값을 출력하시오. # 풀이 오늘도 DP 풀이! 바로 정답 소스 코드를 확인해보자. #include #include using namespace std; int main(){ int n; cin >> n; int D[n+1] = {}; D[1] = 0; for(int i = 2; i < n+1; i++){ D[i] = D[i-1] + 1; if(i%2 == 0) D[i] = min(D[i], D[i/2]+1); if(i%3..

# 문제 위 그림은 크기가 5인 정수 삼각형의 한 모습이다. 맨 위층 7부터 시작해서 아래에 있는 수 중 하나를 선택하여 아래층으로 내려올 때, 이제까지 선택된 수의 합이 최대가 되는 경로를 구하는 프로그램을 작성하라. 아래층에 있는 수는 현재 층에서 선택된 수의 대각선 왼쪽 또는 대각선 오른쪽에 있는 것 중에서만 선택할 수 있다. 삼각형의 크기는 1 이상 500 이하이다. 삼각형을 이루고 있는 각 수는 모두 정수이며, 범위는 0 이상 9999 이하이다. # 풀이 지난 번에 DP 찍먹을 해봤다면 이번에는 아주아주 조금 더 심화! 내 생각엔 언제나 DP로 구현하기 > input[i][j]; } } int D[502][502] = {}; // DP 테이블 생성 및 초기값 할당 D[1][1] = input[1..

# 문제 탁자 위에 돌 N개가 있다. 상근이와 창영이는 턴을 번갈아가면서 돌을 가져가며, 돌은 1개 또는 3개 가져갈 수 있다. 마지막 돌을 가져가는 사람이 게임을 이기게 된다. 두 사람이 완벽하게 게임을 했을 때, 이기는 사람을 구하는 프로그램을 작성하시오. 게임은 상근이가 먼저 시작한다. # 풀이1 간만에 돌아온 알고리즘 풀이 해당 문제는 아주 간단하게 풀 수도 있지만 다이나믹 프로그래밍 DP로도 풀어볼 수 있다. 약간 DP 맛보기 문제랄까? 우선 아주 간단하게 푸는 방법 먼저 확인해보자. #include using namespace std; int main(){ int n; cin >> n; if(n%2 == 0) cout n; const int MAX = 1001; int D[MAX]; // DP..