선택은 나의 것

문제 BOJ 1439 : https://www.acmicpc.net/problem/1439 1439번: 뒤집기 다솜이는 0과 1로만 이루어진 문자열 S를 가지고 있다. 다솜이는 이 문자열 S에 있는 모든 숫자를 전부 같게 만들려고 한다. 다솜이가 할 수 있는 행동은 S에서 연속된 하나 이상의 숫자를 잡고 모 www.acmicpc.net 접근 연속된 숫자를 한 번에 뒤집을 수 있음으로 0과 1의 연속된 부분의 개수가 더 적은 것을 찾는 간단한 문제이다. 코드 // algorithm study // BOJ_1439_뒤집기 #include #include using namespace std; int main() { string s; cin >> s; int count0 = 0, count1 = 0; char ..

문제 BOJ 1715 : https://www.acmicpc.net/problem/1715 1715번: 카드 정렬하기 정렬된 두 묶음의 숫자 카드가 있다고 하자. 각 묶음의 카드의 수를 A, B라 하면 보통 두 묶음을 합쳐서 하나로 만드는 데에는 A+B 번의 비교를 해야 한다. 이를테면, 20장의 숫자 카드 묶음과 30장�� www.acmicpc.net 접근 카드를 합칠 때 적은 수의 카드 묶음을 합쳐나가는 방식이 최소 비교 횟수이다. 따라서 오름차순으로 정렬된 우선순위 큐에 카드 묶음들을 넣어준 다음 top에 있는 두 카드 묶음을 합쳐주면 자연스레 작은 수의 카드 묶음을 더해나갈 수 있다. 이때 두 개의 카드 묶음을 합쳐서 만들어지는 새로운 카드 묶음을 다시 큐에 넣어주는 것을 잊지 말자. 이렇게 진행..

문제 BOJ 1700 : https://www.acmicpc.net/problem/1700 1700번: 멀티탭 스케줄링 기숙사에서 살고 있는 준규는 한 개의 멀티탭을 이용하고 있다. 준규는 키보드, 헤어드라이기, 핸드폰 충전기, 디지털 카메라 충전기 등 여러 개의 전기용품을 사용하면서 어쩔 수 없이 각종 전 www.acmicpc.net 접근 멀티탭에 플러그를 빼는 횟수의 최솟값을 구하는 문제로 그리디 알고리즘(Greedy algorithm)을 통해 문제를 해결할 수 있다. 경우는 세 가지 경우가 있는데 1. 멀티탭에 이미 플러그가 꽂혀있는 경우 2. 멀티탭에 빈자리가 있는 경우 3. 멀티탭이 가득 차 있어 하나를 빼고 플러그를 꽂아야 하는 경우 이렇게 나뉜다. 1, 2번 같은 경우는 기능을 그대로 구현해..

문제 BOJ 2230 : https://www.acmicpc.net/problem/2230 2230번: 수 고르기 첫째 줄에 두 정수 N, M(0≤M≤2,000,000,000)이 주어진다. 다음 N개의 줄에는 차례로 A[1], A[2], …, A[N]이 주어진다. 각각의 A[i]는 0 ≤ |A[i]| ≤ 1,000,000,000을 만족한다. www.acmicpc.net 접근 투 포인터(Two Pointers) 알고리즘을 이용하여 문제를 해결하였다. 이때 배열은 정렬되어 있어야 한다. start와 end 포인터가 가리키는 배열 값의 차가 m이상인지 검사하여 답을 찾을 수 있다. 코드 #include #include using namespace std; int main() { int n, m, num[100..

문제 BOJ 1713 : https://www.acmicpc.net/problem/1713 1713번: 후보 추천하기 첫째 줄에는 사진틀의 개수 N이 주어진다. (1≤N≤20) 둘째 줄에는 전체 학생의 총 추천 횟수가 주어지고, 셋째 줄에는 추천받은 학생을 나타내는 번호가 빈 칸을 사이에 두고 추천받은 순서대로 � www.acmicpc.net 접근 이 문제는 시뮬레이션 문제로 제시하는 조건대로 구현해주면 된다. 이때 조건이 많다면 빠트리고 구현한 게 없는지 확인하는걸 잊지 말자. 우리는 사진틀이 꽉 찼을 때 득표수가 작은 학생부터 밀어낸다. 이때 가장 작은 득표수를 가진 학생이 두 명 이상이라면 그중 사진틀에 먼저 걸린 학생을 밀어내야 하므로 언제 사진틀에 걸렸는지 기억할 필요가 있다. 따라서 배열을 2..

문제 BOJ 10546 : https://www.acmicpc.net/problem/10546 10546번: 배부른 마라토너 문제 마라토너라면 국적과 나이를 불문하고 누구나 참가하고 싶어하는 백준 마라톤 대회가 열린다. 42.195km를 달리는 이 마라톤은 모두가 참가하고 싶어했던 만큼 매년 모두가 완주해왔다. 단, www.acmicpc.net 접근 이 문제에서 배부른 마라토너는 단 한 명이다. 따라서 참가자를 전부 받은 다음 완주한 사람을 빼주면 배부른 마라토너만이 남을 것이다. 이때 동명이인은 map의 second인자를 통해 카운트해줬다. 코드 // algorithm study // BOJ_10546 배부른 마라토너 #include #include using namespace std; int main..