반응형 Problem Solving/백준53 백준 2515 : 전시장 https://www.acmicpc.net/problem/2515 2515번: 전시장 첫째 줄에는 그림의 개수 N (1 ≤ N ≤ 300,000)과 판매가능 그림을 정의하는 1이상의 정수 S가 빈칸을 사이에 두고 주어진다. 다음 이어지는 N개의 줄 각각에는 한 그림의 높이와 가격을 나타내는 정 www.acmicpc.net [ 문제풀이 ] 최적화 문제는 그리디, DP, 파라메트릭 서치 중 하나라고 생각하기 때문에 이 문제 역시 이들을 기반으로 접근하였다. 먼저 그리디이다. 그리디는 매 순간의 선택이 최적해라는 것이 보장되어야 하는데 이는 성립하지 않는다는 것을 반례를 통해 쉽게 찾을 수 있다. 다음으로 파라메트릭 서치이다. 구하고자 하는 금액을 이분 탐색을 시도하면서 진행해야 하는데 현재 key값인 금액이.. 2021. 8. 17. 백준 1727 : 커플 만들기 https://www.acmicpc.net/problem/1727 1727번: 커플 만들기 첫째 줄에 n, m(1≤n, m≤1,000)이 주어진다. 다음 줄에는 n명의 남자들의 성격이 주어진다. 그 다음 줄에는 m명의 여자들의 성격이 주어진다. 성격은 1,000,000이하의 자연수이다. www.acmicpc.net [ 문제풀이 ] 최적화 문제는 그리디, DP, 파라메트릭 서치 중 하나라고 생각하기 때문에 처음에는 그리디로 접근하였는데 틀렸습니다가 나와서 DP로 해결하였다. 먼저 dp 테이블을 다음과 같이 정의하자. dp[i][j] : (1~i)까지의 남자와 (1~j)까지의 여자를 커플 매칭했을때 성격 차이 최소값 그렇다면 점화식은 어떻게 될까? 남자(i), 여자(j)의 수가 같다면 모두 커플이 이루어져야.. 2021. 8. 16. 백준 1275 : 커피숍2 https://www.acmicpc.net/problem/1275 1275번: 커피숍2 첫째 줄에 수의 개수 N과 턴의 개수 Q가 주어진다.(1 ≤ N, Q ≤ 100,000) 둘째 줄에는 처음 배열에 들어가 있는 정수 N개가 주어진다. 세 번째 줄에서 Q+2번째 줄까지는 x y a b의 형식으로 x~y까지의 합 www.acmicpc.net [ 문제풀이 ] 전형적인 세그먼트 트리를 이용해서 구간합을 구하는 문제이다. 세그먼트 자료구조를 공부하였다면 쉽게 해결할 수 있다. 세그먼트 트리 자료구조를 모르거나 공부하고 싶다면 아래 글을 참고하길 바란다. https://sorjfkrh5078.tistory.com/14?category=1007493 세그먼트 트리(Segment Tree) 이번에 배워볼 자료구조는.. 2021. 8. 14. 백준 1300 : K번째 수 https://www.acmicpc.net/problem/1300 1300번: K번째 수 세준이는 크기가 N×N인 배열 A를 만들었다. 배열에 들어있는 수 A[i][j] = i×j 이다. 이 수를 일차원 배열 B에 넣으면 B의 크기는 N×N이 된다. B를 오름차순 정렬했을 때, B[k]를 구해보자. 배열 A와 B www.acmicpc.net [ 문제풀이 ] N이 최대 100000이기 때문에 모든 수를 구해서 정렬한다면 TLE가 발생할 것이다. 이를 현재 숫자가 key라고 할때, key 보다 작거나 같은 수가 k개 이상인지를 판단하는 결정 문제로 변환하여 파라메트릭 서치를 활용하면 해결할 수 있다. 이때 주의해야할 점은 구한 수가 key랑 같다고 끝내버리면 안 된다. 왜냐하면 현재 수인 key가 실제 존재.. 2021. 8. 12. 백준 17244 : 아맞다우산 https://www.acmicpc.net/problem/17244 17244번: 아맞다우산 경재씨는 저녁 약속을 가기 전 챙기지 않은 물건들이 있는 지 확인하고 있다. 필요한 물건은 전부 챙긴 것 같았고 외출 후 돌아오는 길에 경재씨는 외쳤다. "아 맞다 우산!!!" 경재 씨는 매번 외출 www.acmicpc.net [ 문제풀이 ] 전형적인 bfs + 비트마스킹 문제로 챙긴 물건의 상태를 표현하여 중복방문을 체크해주면서 목적지까지 도달하면 되는 문제이다. 물건이 최대 5개이고 맵이 최대 50x50이기 때문에 비트마스킹을 모른다고 하여도 물건을 차례대로 선택하는 모든 경우의 수를 탐색해도 통과될 것 같긴 하다. import java.io.BufferedReader; import java.io.Buffer.. 2021. 8. 11. 백준 7453 : 합이 0인 네 정수 https://www.acmicpc.net/problem/7453 7453번: 합이 0인 네 정수 첫째 줄에 배열의 크기 n (1 ≤ n ≤ 4000)이 주어진다. 다음 n개 줄에는 A, B, C, D에 포함되는 정수가 공백으로 구분되어져서 주어진다. 배열에 들어있는 정수의 절댓값은 최대 228이다. www.acmicpc.net [ 문제풀이 ] N이 최대 4000이기 때문에 모든 경우를 구한다면 N^4으로 시간 초과가 발생하게 된다. 그렇다면 시간 복잡도를 낮춰야 하는데 이런 유형의 문제를 풀어봤다면 투포인터나 이분 탐색으로 해결할 수 있다는 것을 알 수 있다. A, B와 C, D를 나눠서 각각 모든 데이터의 합을 만들어서 저장한 후, AB 합 데이터를 돌면서 CD 합 데이터에서 lowerBound와 u.. 2021. 8. 10. 백준 16434 : 드래곤 앤 던전 https://www.acmicpc.net/problem/16434 16434번: 드래곤 앤 던전 첫 번째 줄에 방의 개수 N (1 ≤ N ≤ 123,456) 과 용사의 초기 공격력 HATK (1 ≤ HATK ≤ 1,000,000) 가 주어집니다. i+1번째 줄엔 i번째 방의 정보를 나타내는 세개의 정수 ti, ai, hi (ti ∈ {1, 2}, 1 www.acmicpc.net [ 문제풀이 ] 최솟값을 찾는 최적화 문제이기 때문에 파라메트릭 서치를 활용하면 해결할 수 있다. 요새 파라메트릭 서치 문제를 자주 풀어서 그런지 최적 값을 구하는 문제를 보면 자연스럽게 dp, 그리디, 파라메트릭 서치 중 하나를 떠올리게 되는 것 같다. 주의해야할 점은 포션을 먹어도 Hmaxhp를 넘길 수 없는 조건과 용사가 .. 2021. 8. 9. 백준 1484 : 다이어트 https://www.acmicpc.net/problem/1484 1484번: 다이어트 첫째 줄부터 한 줄에 하나씩 가능한 성원이의 현재 몸무게를 오름차순으로 출력한다. 가능한 몸무게가 없을 때는 -1을 출력한다. 현재 몸무게는 자연수로 떨어지지 않을 수도 있는데, 이런 경우 www.acmicpc.net [ 문제풀이 ] 수학적으로 접근하면 쉽게 해결할 수 있는 문제이다.현재 몸무게를 x, 기억하고 있던 몸무게를 y로 둔다면 다음과 같이 표현할 수 있다. G = x^2 - y^2 이를 풀어보면 다음과 같으며 결국 (x+y)와 (x-y)는 G의 약수여야 한다는 것을 알 수 있다. G = (x+y)(x-y) 따라서 루트 G부터 1까지 차례대로 탐색해주면서 G의 약수를 찾아주면 된다. 주의해야 할 점은 우리가 .. 2021. 8. 8. 백준 1647 : 도시 분할 계획 https://www.acmicpc.net/problem/1647 1647번: 도시 분할 계획 첫째 줄에 집의 개수N, 길의 개수M이 주어진다. N은 2이상 100,000이하인 정수이고, M은 1이상 1,000,000이하인 정수이다. 그 다음 줄부터 M줄에 걸쳐 길의 정보가 A B C 세 개의 정수로 주어지는데 A번 집 www.acmicpc.net [ 문제풀이 ] 기본적으로 MST를 활용해야 하는 문제이다. 다만, N이 최대 100,000이기때문에 마을을 두 그룹으로 분할할 수 있는 모든 경우에 MST를 적용한다면 당연히 TLE가 발생할 것이다. 주어진 예제로 정답 8인 경로를 만들어보면 (N-1)개의 정점까지만 MST를 구성해주면 된다는 것을 알 수 있다. 왜냐하면 (N-1)개의 정점(마을 1)까지의 .. 2021. 8. 7. 이전 1 2 3 4 5 6 다음 반응형