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..

# 문제 두 개의 자연수를 입력받아 최대 공약수와 최소 공배수를 출력하는 프로그램을 작성하시오. # 풀이 유클리드 호제법을 이용해 푸는 문제다. 1. 두 수 중에서 큰 수를 a, 작은 수를 b라고 하고 a를 b로 나눈다. 2. a가 b로 나누어떨어지면 두 수의 최대공약수는 b이다. 3. a가 b로 나누어떨어지지 않으면 a를 b로 나눈 나머지와 b에 대하여 1번부터 다시 반복한다. 출처: 생활코딩 C언어의 기초 문법 그림으로 다시 한번 확인해보자. 246과 183의 최대공약수를 구하고자 한다. 더 큰 수인 246을 a로 놓고 183을 b로 놓은 후 a%b로 나머지 연산을 한다. 나머지(r)가 0이 아니므로 b를 a로, 나머지(r)를 b로 놓고 다시 나머지 연산을 수행한다. 나머지가 0일때까지 해당 연산을 ..

# 문제 N이 주어졌을 때, 제일 마지막에 남게 되는 카드를 구하는 프로그램을 작성하시오. # 풀이 '우선, 제일 위에 있는 카드를 바닥에 버린다'에서 우리는 queue를 사용해 푸는 문제라는 걸 파악할 수 있다. 바로 정답 소스코드를 확인해보자. #include #include using namespace std; int main(){ int n; cin >> n; queue set; for(int i=1; i

# 문제 어떤 단어를 뒤에서부터 읽어도 똑같다면 그 단어를 팰린드롬이라고 한다. 'radar', 'sees'는 팰린드롬이다. 수도 팰린드롬으로 취급할 수 있다. 수의 숫자들을 뒤에서부터 읽어도 같다면 그 수는 팰린드롬수다. 121, 12421 등은 팰린드롬수다. 123, 1231은 뒤에서부터 읽으면 다르므로 팰린드롬수가 아니다. # 풀이 팰린드롬 수인지 확인하는 문제! 반복문을 통해 확인하는 방법과 헤더에 정의된 reverse() 함수를 이용한 방법, 총 두 가지를 소개하려고 한다. 우선 반복문을 이용하는 방법 먼저 정답 소스코드를 확인해보자. #include using namespace std; int main(){ ios_base::sync_with_stdio(false);// 두 표준 입출력 동기화..

# 문제 N개의 정수 A[1], A[2], …, A[N]이 주어져 있을 때, 이 안에 X라는 정수가 존재하는지 알아내는 프로그램을 작성하시오. # 풀이 이진 탐색 문제! 이진 탐색을 사용하는 첫 문제인만큼 직접 구현한 풀이 하나, algorithm 헤더에 구현된 이진 탐색 함수를 사용한 풀이 하나 총 두 개의 풀이를 업로드하려고 한다. 정답 소스코드를 보며 확인해보자. #include #include using namespace std; int binarySearch(int len, int m, int arr[]); int main(){ ios_base::sync_with_stdio(false);// 두 표준 입출력 동기화 해제 cin.tie(NULL);// 입력과 출력 묶음을 풀기 int n; cin ..

# 문제 N개의 수가 주어졌을 때, 이를 오름차순으로 정렬하는 프로그램을 작성하시오. # 풀이 [시간 복잡도가 O(nlogn)인 정렬 알고리즘으로 풀 수 있습니다. 예를 들면 병합 정렬, 힙 정렬 등이 있지만, 어려운 알고리즘이므로 지금은 언어에 내장된 정렬 함수를 쓰는 것을 추천드립니다.]라는 메시지를 기억하고 풀어야 하는 문제다. 풀이를 진행하는 C++의 경우 STL을 사용해서 문제를 풀면 되는데 STL이 무엇인지 간단하게 확인하고 넘어가자. STL이란 표준 템플릿 라이브러리로 일반적인 알고리즘들에 대한 효율적인 구현을 제공한다. 다시 말해 많은 프로그래머들이 공통적으로 사용하는 자료구조와 알고리즘 등을 템플릿으로 구현한 클래스로써 STL의 사용을 통해 개발 효율을 크게 향상시킬 수 있다. STL의 ..

# 문제 상근이가 설탕을 정확하게 N킬로그램 배달해야 할 때, 봉지 몇 개를 가져가면 되는지 그 수를 구하는 프로그램을 작성하시오. # 풀이 [한때는 이 문제가 "기본 수학 1" 단계에 있었지만, 사실 브루트 포스로 푸는 게 더 쉽습니다.]라고 한다. 브루트 포스로 풀어보자. 그럼 바로 정답 소스코드부터 확인! #include using namespace std; int main(){ int n; cin >> n; int cnt = 0; bool done = 0; while(n >= 0){ if(n%5 == 0){ cnt += n/5; done = 1; break; } n -= 3; cnt++; } if(!done) cout

# 문제 숌이 만든 N번째 영화의 제목에 들어간 수를 출력하는 프로그램을 작성하시오. 숌은 이 시리즈를 항상 차례대로 만들고, 다른 영화는 만들지 않는다. # 풀이 이번에도 역시 브루트포스 문제다. 바로 정답 소스코드 확인! #include using namespace std; bool checkSixNum(int n); int main(){ int n; cin >> n; int numbering = 666; int series = 1; bool numCheck; if(n == 1) cout 0) { if (n%10 == 6) { cnt++; if (cnt == 3) return true; } else cnt = 0; n /= 10; } return false; } 종말의 수는 6이 적어도 3개 이상 연..