본문 바로가기

문제 노트

 (157)
구간 합 구하기 3( BOJ 11658 ) 문제 11658. 구간 합 구하기 3 : https://www.acmicpc.net/problem/11658 11658번: 구간 합 구하기 3 첫째 줄에 표의 크기 N과 수행해야 하는 연산의 수 M이 주어진다. (1 ≤ N ≤ 1024, 1 ≤ M ≤ 100,000) 둘째 줄부터 N개의 줄에는 표에 채워져있는 수가 1행부터 차례대로 주어진다. 다음 M개의 줄에는 www.acmicpc.net 문제 이해하기 2차원 표에서 구간의 합을 구해야 합니다. 합을 구하는 문제이기 때문에 펜윅트리를 사용할 수 있습니다. 하지만 1차원 배열을 활용한 펜윅트리로는 제한된 시간 안에 해결할 수 없습니다. 데이터가 2차원 표이기 때문에 제한시간 내 해결하기 위해서는 2차원 펜윅트리(2D 펜윅트리)를 만들어야 합니다. 문제 해..
굉장한 학생( BOJ 2336 ) 문제 2336. 굉장한 학생 : https://www.acmicpc.net/problem/2336 2336번: 굉장한 학생 첫째 줄에 N(1 ≤ N ≤ 500,000)이 주어진다. 다음 세 개의 줄에는 각 시험에서 1등인 학생부터 N등인 학생이 순서대로 주어진다. 학생의 번호는 1부터 N까지 매겨져 있다. www.acmicpc.net 문제 파악하기 나보다 모든 시험을 잘 본 학생이 없는 경우, 굉장한 학생이 됩니다. N이 500,000이기 때문에 단순 for문으로는 힘듭니다. 이 경우, 세그먼트 트리를 차근차근 채워넣으면 문제를 해결할 수 있습니다. 문제 해결하기 우선 첫번째 시험 결과 순서대로 세그먼트 트리에 값을 저장합니다. 세그먼트 트리에 저장하는 위치는 두번째 시험을 기준으로 합니다. 두번째 시험..
체인점( BOJ 2472 ) 문제 2472. 체인점 : https://www.acmicpc.net/problem/2472 2472번: 체인점 첫째 줄에는 매장 후보지의 개수를 나타내는 정수 N이 입력된다(1≤N≤100,000). 매장 후보지들은 1부터 N까지의 번호로 구분된다. 둘째 줄에는 아파트 단지의 위치를 나타내는 세 개의 정수 A, B, C www.acmicpc.net 문제 파악하기 아파트는 A, B, C로 총 3개의 노드가 주어집니다. 후보지 p에서 A, B, C까지의 거리가 후보지 q에서 A, B, C까지의 거리보다 모두 먼 경우, 후보지 p에는 매장을 설치하지 않습니다. 후보지에 매장을 설치할 수 있는지 여부를 알기 위해서는 후보지마다 A, B, C까지의 거리를 구해야 합니다. 거리는 음수가 나오지 않기에 가장 빠른 다..
Fine Dining( BOJ 16763 ) 문제 16763. Fine Dining : https://www.acmicpc.net/problem/16763 16763번: Fine Dining In this example, the cow in pasture 3 should stop for a meal, since her route would only increase by 6 (from 2 to 8), and this increase is at most the yumminess 7 of the haybale. The cow in pasture 2 should obviously eat the hay in pasture 2, since this ca www.acmicpc.net 문제 파악하기 (n-1)마리의 소들은 각각 1 ~ (N-1)번 초원에 있으며 ..
Cowpatibility( BOJ 16764 ) 문제 16764. Cowpatibility : https://www.acmicpc.net/problem/16764 16764번: Cowpatibility Here, cow 4 is not compatible with any of cows 1, 2, or 3, and cows 1 and 3 are also not compatible. www.acmicpc.net 문제 파악하기 친구가 될 수 없는 소들의 쌍을 찾는 문제입니다. 아이스크림의 맛은 총 5개 입력되며, 단순히 중첩 반복문을 사용하기에는 N의 값이 너무 큽니다. 단순히 아이스크림 맛을 카운트하기에는 중복되는 소들을 계산할 수 없습니다. 이 문제는 map 자료형을 사용해야 합니다. 문제 해결하기 #1 map은 탐색에 필요한 키값과 해당 키값에 할당된..
사탕 가게( BOJ 4781 ) 문제 4781. 사탕 가게 : https://www.acmicpc.net/problem/4781 4781번: 사탕 가게 각 테스트 케이스의 첫째 줄에는 가게에 있는 사탕 종류의 수 n과 상근이가 가지고 있는 돈의 양 m이 주어진다. (1 ≤ n ≤ 5,000, 0.01 ≤ m ≤ 100.00) m은 항상 소수점 둘째자리까지 주어진다. 다음 n개 www.acmicpc.net 문제 파악하기 주어진 자금 내에서 가장 높은 칼로리를 얻을 수 있도록 사탕을 구매해야 하는 문제입니다. 여러모로 냅색 문제와 유사하지만 사탕을 원하는만큼 구입할 수 있다는 차이점이 있습니다. 그렇다고 무작정 반복문을 돌리면 3중 반복문이 나오기에 시간초과가 걸립니다. 수행 시간을 줄이기 위해서는 기본 냅색 문제의 점화식을 수정해야 합니..
터보소트( BOJ 3006 ) 문제 3006. 터보소트 : https://www.acmicpc.net/problem/3006 3006번: 터보소트 첫째 줄에 N이 주어진다. N은 1보다 크거나 같고, 100,000보다 작거나 같은 자연수이며, 배열의 크기이다. 둘째 줄부터 N개의 줄에는 1보다 크거나 같고, N보다 작거나 같은 수가 중복 없이 주어진다 www.acmicpc.net 문제 파악하기 시작 부분과 종료 지점을 번갈아가면서 정렬을 할 때, 교환되는 횟수를 구하는 문제입니다. 버블 정렬을 기반으로 진행하기 때문에 현재 위치와 정렬되었을 때의 위치의 차이가 핵심요소가 될 수 있습니다. 현재 위치에서 원하는 위치까지 가는데 얼만큼 숫자를 교환해야 할까요? 문제 해결하기 정답은 세그먼트 트리를 이용하는 것입니다. 입력된 위치와 정렬했..
숫자 게임( BOJ 2923 ) 문제 2923. 숫자 게임 : https://www.acmicpc.net/problem/2923 2923번: 숫자 게임 창영이와 현우는 새로운 게임을 하고 있다. 이 게임은 여러 라운드로 이루어져 있다. 매 라운드가 시작할 때, 현우는 창영이에게 100보다 작은 두 숫자 A와 B를 말해준다. 그러고 난 뒤, 창영이는 www.acmicpc.net 문제 파악하기 ai + bi의 최댓값을 가장 작게 만들기 위해서는 한쪽에서는 최솟값만, 한쪽에서는 최댓값만 선택해서 더하면 됩니다. 예를 들어 a에 (1, 2, 3)이 있고, b에 (1, 4, 8)이 숫자는 (1, 8) / (2, 4) / (3, 1) 순으로 짝지어지며 이 때 9가 최댓값이 됩니다. 문제는 데이터가 최대 100,000개라는 점입니다. 어떻게 해야 ..

티스토리툴바