본문 바로가기

분류 전체보기

(191)
사탕 가게( 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개라는 점입니다. 어떻게 해야 ..
흙길 보수하기( BOJ 1911 ) 문제 흙길 보수하기 : https://www.acmicpc.net/problem/1911 1911번: 흙길 보수하기 어젯밤 겨울 캠프 장소에서 월드 본원까지 이어지는, 흙으로 된 비밀길 위에 폭우가 내려서 N (1
The King of the North( BOJ 9209 ) 문제 9209. The king of the north : https://www.acmicpc.net/problem/9209 9209번: The King of the North The input is given in the form of the (rectangular) strategic map which your advisors came up with. Every square in map is assigned a number of bannermen which would be required to defend the position against any potential army. The map is formatted as fol www.acmicpc.net 문제 파악하기 격자칸마다 해당 지력을 지키기 위..
Cops and Robbers( BOJ 16407 ) 문제 16407. Cops and Robbers : https://www.acmicpc.net/problem/16407 16407번: Cops and Robbers The first line contains three integers n, m, and c (1 ≤ n, m ≤ 30, 1 ≤ c ≤ 26): the dimensions of the grid representing Calirado, and the number of different terrain types. Then follows m lines of exactly n characters each: the map of Calirado. Eac www.acmicpc.net 문제 파악하기 은행에서 도둑들이 탈풀하지 못 하게 바리케이트를 쌓아야 합니..
초등 수학( BOJ 11670 ) 문제 11670. 초등수학 : https://www.acmicpc.net/problem/11670 11670번: 초등 수학 입력과 같은 순서대로 (a,b) 순서쌍이 유효한 방정식과 함께 출력된다. 각각의 방정식은 5개의 요소로 나뉜다. a와 3개의 연산자(+ 혹은 - 혹은 *)중 하나, b 그리고 = 와 연산결과이다. 모든 연 www.acmicpc.net 문제 파악하기 모든 입력값은 항상 3가지 결괏값을 가질 수 있습니다. 입력된 모든 값이 서로 다른 결괏값을 가질 수 있는지와 다르다면 어떻게 다른지 출력하는 문제입니다. 입력되는 값이 10-6 ~ 106 사이의 정수이기 때문에 int형보다는 long long int형이 계산하기 편해 보입니다. 입력 값이 하나의 결과에 대응되어야 하기 때문에 이분 매칭 ..
피타고라스 수( BOJ 14398 ) 문제 14398. 피타고라스 수 : https://www.acmicpc.net/problem/14398 14398번: 피타고라스 수 피타고라스 수 (a, b, c)는 다음과 같은 조건을 만족하는 세 쌍이다. a, b, c는 정수이다. a^2 + b^2 = c^2 a와 b의 최대 공약수는 1이다. 영선이는 나무 막대 N개를 가지고 있다. 영선이는 직각 삼각형 모 www.acmicpc.net 문제 파악하기 피타고라스 수란 a2 + b2 = c2을 만족하는 (a, b, c) 숫자쌍을 의미합니다. 이 문제에서는 서로 서로소인 a와 b를 찾는 문제입니다. (a, b) 순서쌍의 최대 개수를 묻고 있기 때문에 이분 매칭을 이용해야 한다는 점을 유추할 수 있습니다. 이분 탐색을 위해서는 2개의 범주로 나눠야 합니다. ..