Carrot Farming

# 문제 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개 이상 연..

# 문제 보드가 체스판처럼 칠해져 있다는 보장이 없어서, 지민이는 8×8 크기의 체스판으로 잘라낸 후에 몇 개의 정사각형을 다시 칠해야겠다고 생각했다. 당연히 8*8 크기는 아무데서나 골라도 된다. 지민이가 다시 칠해야 하는 정사각형의 최소 개수를 구하는 프로그램을 작성하시오. # 풀이 문제를 잘 읽자 100번 깜지 쓰겠습니다. 그냥 다시 색칠 보자마자 예전에 과제로 구현했던 코드 풀이랑 비슷할 것 같아 냅다 요상망측하게 구현하고 테스트 케이스 넣어보고 깨달았습니다. 8*8이라고요... 여러가지로 따져볼 게 있었던 브루트포스 문제다. 생각을 열심히 하면서 풀어보자. 바로 정답 소스코드부터 확인! #include #include using namespace std; // 비교할 체스판 문양 2개를 미리 s..

# 문제 두 정수 A와 B를 입력받은 다음, A/B를 출력하는 프로그램을 작성하시오. # 풀이 이번에도 브루트포스 문제다. 모든 경우를 탐색한다고 생각하면 오히려 구현하기가 쉬우니 천천히 생각하며 풀어보자. 바로 정답 소스코드 확인! #include using namespace std; int decompositionSum(int n); int main(){ int n; cin >> n; int m = 1; bool print = 0; while(m < n){ if(n == decompositionSum(m)){ print = 1; cout 0){ sum += n%10; n /= 10; } return sum; } 분해합을 구해주는 decompositionSum함수를 먼저 살펴보자. int 타입을 반환하..

# 문제 N장의 카드에 써져 있는 숫자가 주어졌을 때, M을 넘지 않으면서 M에 최대한 가까운 카드 3장의 합을 구해 출력하시오. # 풀이 solved.ac 클래스 2에 속하고 백준 단계별 풀이로는 브루트 포스에 해당하는 문제! 정답 소스코드를 보며 필요한 개념을 정리해보자. 우선 브루트포스 알고리즘이란 완전탐색 알고리즘이다. 즉, 모든 경우의 수를 전수조사하여 정답을 찾아낸다. 어떻게 보면 가장 기본적이고도 핵심적인 방법이지만, 코드 수행시간이나 메모리 측면에서 효율이 떨어진다. 그래도 다른 효율적인 해결 방법을 알아보기 위해서라면 꼭 한번쯤 생각해보고 넘어가야 하는 단계! 바로 정답 소스코드를 확인해보자. #include using namespace std; int main(){ int n, m; c..

# 문제 여러분이 작성할 프로그램은 초기에 모든 방이 비어있다고 가정하에 이 정책에 따라 N 번째로 도착한 손님에게 배정될 방 번호를 계산하는 프로그램이다. 첫 번째 손님은 101 호, 두 번째 손님은 201 호 등과 같이 배정한다. 그림 1 의 경우를 예로 들면, H = 6이므로 10 번째 손님은 402 호에 배정해야 한다. # 풀이 복잡해보이지만 천천히 뜯어보면 어렵지 않은 문제다. 정답 소스코드를 확인하기 전, 방이 어떤 순서로 배정되는지 살펴보자. 손님의 선호에 관한 정보는 다음과 같다. 손님은 엘리베이터를 타고 이동하는 거리는 신경 쓰지 않는다. 다만 걷는 거리가 같을 때에는 아래층의 방을 더 선호한다. 예를 들면 102 호 방보다는 301 호 방을 더 선호하는데, 102 호는 거리 2 만큼 걸..