본문 바로가기

전체 글153

[백준/C,C++] 1049번: 기타줄 www.acmicpc.net/problem/1049 1049번: 기타줄 첫째 줄에 N과 M이 주어진다. N은 100보다 작거나 같은 자연수이고, M은 50보다 작거나 같은 자연수이다. 둘째 줄부터 M개의 줄에는 각 브랜드의 패키지 가격과 낱개의 가격이 공백으로 구분하여 주 www.acmicpc.net 풀이 살짝 헷갈리는 문제입니다. 경우를 잘 따져야 하는데요.. 크게 2가지로 나눌 수 있습니다. 패키지 가격보다 낱개 6개의 가격이 더 낮은 경우, 낱개로 모두 구매하는 것이 최소 가격입니다. 하지만 패키지 가격이 낱개 6개의 가격보다 더 낮은 경우가 중요합니다. 어쨌든 필요한 기타 줄이 6개 이상이라면 그만큼은 무조건 패키지를 사는 것이 최소 가격일 겁니다. 하지만 패키지를 살 수 있는 만큼 모두 구매한 .. 2021. 4. 20.
[백준/C,C++] 10815번: 숫자 카드 www.acmicpc.net/problem/10815 10815번: 숫자 카드 첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10, www.acmicpc.net 풀이 기본적인 이분 탐색 문제입니다. #include #include #include using namespace std; int n, m; bool search(const vector& v, int num) { int left = 0, right = n - 1, mid; while (left num) right = mid - 1; else if (v[mid] < num) left.. 2021. 4. 20.
[백준/C,C++] 1654번: 랜선 자르기 www.acmicpc.net/problem/1654 1654번: 랜선 자르기 첫째 줄에는 오영식이 이미 가지고 있는 랜선의 개수 K, 그리고 필요한 랜선의 개수 N이 입력된다. K는 1이상 10,000이하의 정수이고, N은 1이상 1,000,000이하의 정수이다. 그리고 항상 K ≦ N 이다. 그 www.acmicpc.net 풀이 이분 탐색으로 푸는 문제입니다. 예제 입력으로 보면 4 11 802 743 457 539 에서 1을 최소로, 802(가장 큰 값)를 최대로 두고 이분 탐색을 시작하면 되는데, 조건은 해당 값으로 존재하는 랜선을 모두 나누었을 때 필요한 랜선의 개수만큼 나오는지 체크하면 됩니다. #include #include using namespace std; using LL = long l.. 2021. 4. 20.
[백준/C,C++] 7576번: 토마토 www.acmicpc.net/problem/7576 7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토 www.acmicpc.net 풀이 2차원 배열이 주어지는 여타 다른 BFS 문제들과 비슷합니다. 크게 다른 점은 출발 지점이 정해져 있지 않다는 건데요. 익은 토마토, 즉 1인 지점을 모두 시작 지점으로 BFS를 실행시켜야 한다는 겁니다. 6 4 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 과 같은 예제가 입력되었다고 봅시다. 1일이 지난 후 토마토들은 아래와 같게 됩니다. 1 1 .. 2021. 4. 20.

티스토리툴바