알고리즘(71)
-
[백준/C++] 1920번 수 찾기
문제: www.acmicpc.net/problem/1920 1920번: 수 찾기 첫째 줄에 자연수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다. 다음 줄에는 M(1 ≤ M ≤ 100,000)이 주어진다. 다음 줄에는 M개의 수들이 주어지는데, 이 수들 www.acmicpc.net 문제풀이 이진 탐색 문제이다. 배열을 정렬한 후 이진 탐색을 진행하면 된다. 코드 #include #include using namespace std; int main(){ ios::sync_with_stdio(false); cin.tie(NULL); int N; cin>>N; int A[N]; for(int i=0; i>A[i]; sort(A, A+N);..
2021.02.01 -
[백준/C++] 2231번 분해합
문제: www.acmicpc.net/problem/2231 2231번: 분해합 어떤 자연수 N이 있을 때, 그 자연수 N의 분해합은 N과 N을 이루는 각 자리수의 합을 의미한다. 어떤 자연수 M의 분해합이 N인 경우, M을 N의 생성자라 한다. 예를 들어, 245의 분해합은 256(=245+2+4+5)이 www.acmicpc.net 문제풀이 모든 경우의 수를 비교하는 브루트 포스 문제이다. 입력값 N의 최소 생성자를 찾아내야 하는데 나는 1부터 N까지의 수 모두 N의 생성자가 될 수 있는지 여부를 확인해보는 코드를 작성했다. N % 10 과 N /= 10 연산을 이용해 분해합의 필요한 각 자릿수의 덧셈을 하였다. 코드 #include using namespace std; int main(){ ios::s..
2021.02.01 -
[백준/C++] 18111번 마인크래프트
문제: www.acmicpc.net/problem/18111 18111번: 마인크래프트 팀 레드시프트는 대회 준비를 하다가 지루해져서 샌드박스 게임인 ‘마인크래프트’를 켰다. 마인크래프트는 1 × 1 × 1(세로, 가로, 높이) 크기의 블록들로 이루어진 3차원 세계에서 자유롭게 www.acmicpc.net 문제풀이 모든 경우의 수를 비교하는 브루트 포스 문제이다. 먼저 땅의 높이 최솟값과 최댓값을 구한 뒤 땅을 최솟값으로 평탄화할 시의 시간부터 땅을 최댓값으로 평탄화할시의 시간까지 모두 비교하여 결과를 구했다. 만일 인벤토리가 0 미만이라면 물리적으로 평탄화가 불가능하기 때문에 continue() 함수로 패스한다. 코드 #include #include using namespace std; int main..
2021.01.30 -
[백준/C++] 2805번 나무 자르기
문제: www.acmicpc.net/problem/2805 2805번: 나무 자르기 첫째 줄에 나무의 수 N과 상근이가 집으로 가져가려고 하는 나무의 길이 M이 주어진다. (1 ≤ N ≤ 1,000,000, 1 ≤ M ≤ 2,000,000,000) 둘째 줄에는 나무의 높이가 주어진다. 나무의 높이의 합은 항상 M보 www.acmicpc.net 문제풀이 이분 탐색 문제 중에서도 조건을 만족하는 값들 중 최댓값을 구하는 문제이다. (나무길이) - (벌목기 높이)의 총합 >= M 을 만족하는 벌목기 높이의 최댓값을 구해야 한다. 최댓값을 구하기 위해서 위의 조건을 만족하더라도 루프를 멈추지 않고 계속 탐색한다. 코드 #include using namespace std; int main(){ ios::sync_..
2021.01.29 -
[백준/C++] 1966번 프린터큐
문제: www.acmicpc.net/problem/1966 1966번: 프린터 큐 여러분도 알다시피 여러분의 프린터 기기는 여러분이 인쇄하고자 하는 문서를 인쇄 명령을 받은 ‘순서대로’, 즉 먼저 요청된 것을 먼저 인쇄한다. 여러 개의 문서가 쌓인다면 Queue 자료구조에 www.acmicpc.net 문제풀이 첫 번째로 문제에 접근한 방식은 큐와 배열을 선언하여 큐에는 pair로 문서의 인덱스, 중요도를 쌍으로 저장하고 배열에는 중요도를 저장 후 내림차순 정렬(sort 함수)하여 배열과 큐의 중요도를 비교했다. - 중요도가 같을 때 1. 목표 문서라면(인덱스가 같다면) 현재 출력 순서 출력 후 루프 종료 2. 현재 가장 높은 중요도를 가진 문서이므로 pop() 후 출력 순서 증가, 배열 인덱스 증가 - ..
2021.01.29