전체 글
거스름돈 기초 문제
1. 거스름돈 2개를 사용하는 경우 www.acmicpc.net/problem/14916 14916번: 거스름돈 첫째 줄에 거스름돈 액수 n(1 ≤ n ≤ 100,000)이 주어진다. www.acmicpc.net www.acmicpc.net/problem/2839 2839번: 설탕 배달 상근이는 요즘 설탕공장에서 설탕을 배달하고 있다. 상근이는 지금 사탕가게에 설탕을 정확하게 N킬로그램을 배달해야 한다. 설탕공장에서 만드는 설탕은 봉지에 담겨져 있다. 봉지는 3킬로그 www.acmicpc.net 위 두 문제들 처럼 거스름돈의 종류가 2개일때, 최소 갯수로 거스름돈을 반환하는 방식은 1. 두 거스름돈 중 큰 값으로 n 을 나눴을때 나눠 떨어지면, 이 나눗셈의 몫을 카운팅하고 프로그램을 종료한다 2. 큰 거..
BOJ 2304 - 창고 다각형
www.acmicpc.net/problem/2304 2304번: 창고 다각형 첫 줄에는 기둥의 개수를 나타내는 정수 N이 주어진다. N은 1 이상 1,000 이하이다. 그 다음 N 개의 줄에는 각 줄에 각 기둥의 왼쪽 면의 위치를 나타내는 정수 L과 높이를 나타내는 정수 H가 한 개의 www.acmicpc.net - C++ #include #include using namespace std; int N, first = 1001, last, longest, pos, len, answer; int arr[1001]; stack st; int main() { cin.tie(0); ios_base::sync_with_stdio(0); cin >> N; while (N--) { cin >> pos >> len; ..
BOJ 14719 - 빗물
www.acmicpc.net/problem/14719 14719번: 빗물 첫 번째 줄에는 2차원 세계의 세로 길이 H과 2차원 세계의 가로 길이 W가 주어진다. (1 ≤ H, W ≤ 500) 두 번째 줄에는 블록이 쌓인 높이를 의미하는 0이상 H이하의 정수가 2차원 세계의 맨 왼쪽 위치 www.acmicpc.net - C++ #include #include using namespace std; int H, W, answer; int arr[501]; int main() { cin.tie(0); ios_base::sync_with_stdio(0); cin >> H >> W; for (int i = 0; i > arr[i]; for (int i = 1; i = 0; j--) left = max(left, a..
BOJ 1725 - 히스토그램
www.acmicpc.net/problem/1725 1725번: 히스토그램 첫 행에는 N (1 ≤ N ≤ 100,000) 이 주어진다. N은 히스토그램의 가로 칸의 수이다. 다음 N 행에 걸쳐 각 칸의 높이가 왼쪽에서부터 차례대로 주어진다. 각 칸의 높이는 1,000,000,000보다 작거나 같은 www.acmicpc.net - C++ #include #include #include using namespace std; stack st; // histogram's index int arr[100002]; // histogram's height int N, answer; int main() { cin.tie(0); ios_base::sync_with_stdio(0); cin >> N; for (int i ..
BOJ 1935 - 후위 표기식 2
www.acmicpc.net/problem/1935 1935번: 후위 표기식2 첫째 줄에 피연산자의 개수(1 ≤ N ≤ 26) 가 주어진다. 그리고 둘째 줄에는 후위 표기식이 주어진다. (여기서 피연산자는 A~Z의 영대문자이며, A부터 순서대로 N개의 영대문자만이 사용되며, 길이 www.acmicpc.net - C++ #include #include #include using namespace std; stack st; string input; double result; double a_idx, b_idx; int arr[27]; int N; int main() { cin.tie(0); ios_base::sync_with_stdio(0); cin >> N; cin >> input; for (int i =..
BOJ 1238 - 파티
www.acmicpc.net/problem/1238 1238번: 파티 첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 10,000), X가 공백으로 구분되어 입력된다. 두 번째 줄부터 M+1번째 줄까지 i번째 도로의 시작점, 끝점, 그리고 이 도로를 지나는데 필요한 소요시간 Ti가 들어� www.acmicpc.net 다익스트라를 이용해서 오고 가는데 걸리는 시간 중 가장 오래 걸리는 시간을 구해야하는 문제이다. 다른 다익스트라 문제와 다르게 출발지 -> 목적지 -> 출발지 로 복귀해야하며, 그 중 가장 오래 걸리는 시간을 찾아야하는 문제다 - c++ #include #include #include #include #define MAX 10001 #define INF 987654321 usin..
BOJ 1929 - 소수 구하기
www.acmicpc.net/problem/1929 1929번: 소수 구하기 첫째 줄에 자연수 M과 N이 빈 칸을 사이에 두고 주어진다. (1 ≤ M ≤ N ≤ 1,000,000) M이상 N이하의 소수가 하나 이상 있는 입력만 주어진다. www.acmicpc.net 에라토스테네스의 체를 알고 있다면 바로 풀 수 있다 - c++ #include using namespace std; int M, N; int arr[1000001]; void find_prime() { for (int i = 2; i
BOJ 2512 - 예산
www.acmicpc.net/problem/2512 2512번: 예산 첫째 줄에는 지방의 수를 의미하는 정수 N이 주어진다. N은 3 이상 10,000 이하이다. 다음 줄에는 각 지방의 예산요청을 표현하는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 값들은 모두 1 이상 www.acmicpc.net 이분 탐색을 이용해서 풀어야 하는 문제로, 유사한 문제로는 BOJ 1654 랜선 자르기, BOJ 2805 나무 자르기 등 이 있다 위 세문제는, 이분 탐색의 시작점과 끝점이라 할 수 있는 start(low), end(high) 를 일종의 인덱스 값으로 잡고 문제에서 요구하는 연산을 수행한 결과를 가지고 주어진 상한선 M 에 가장 가까이 가는 값을 잡아서 도출해야한다 이 예산 문제에서는 각 지방의 예산 요청..