PS/BOJ
백준 BOJ 2109 순회강연
문제 백준 BOJ 2109 순회강연 https://www.acmicpc.net/problem/2109 2109번: 순회강연 한 저명한 학자에게 n(0 ≤ n ≤ 10,000)개의 대학에서 강연 요청을 해 왔다. 각 대학에서는 d(1 ≤ d ≤ 10,000)일 안에 와서 강연을 해 주면 p(1 ≤ p ≤ 10,000)만큼의 강연료를 지불하겠다고 알려왔다. www.acmicpc.net 사용 알고리즘 Data structures Greedy Sorting Priority queue 풀이 d(마감일) 기준으로 오름차순 정렬 후 차례대로 우선순위큐에 넣을지 말지를 판단. 우선순위큐의 size
백준 BOJ 2616 소형기관차
문제 백준 BOJ 2616 소형기관차 https://www.acmicpc.net/problem/2616 2616번: 소형기관차 첫째 줄에 기관차가 끌고 가던 객차의 수가 입력된다. 그 수는 50,000 이하이다. 둘째 줄에는 기관차가 끌고 가던 객차에 타고 있는 손님의 수가 1번 객차부터 차례로 입력된다. 한 객차에 타고 있 www.acmicpc.net 사용 알고리즘 Dynamic programming Prefix sum 풀이 누적합 + DP. 우선 소형 기관차가 최대로 끌 수 있는 객차의 수에 해당하는 길이의 구간마다 합을 구해 놓고 2차원 DP를 돌림. dp[i][j]=max(dp[i-1][j],dp[i-m][j-1]+b[i]); dp[i][j] = i번째 객차까지 j개의 소형기관차를 썼을 때 최댓값.
백준 BOJ 10800 컬러볼
문제 백준 BOJ 10800 컬러볼 https://www.acmicpc.net/problem/10800 10800번: 컬러볼 첫 줄에는 공의 개수를 나타내는 자연수 N이 주어진다(1 ≤ N ≤ 200,000). 다음 N개의 줄 중 i번째 줄에는 i번째 공의 색을 나타내는 자연수 Ci와 그 크기를 나타내는 자연수 Si가 주어진다(1 ≤ Ci ≤ N www.acmicpc.net 사용 알고리즘 Implementation Sorting Prefix sum 풀이 {크기, 색깔, index} 를 원소로 하는 3진 pair를 만들어 크기를 기준으로 정렬. 누적 합을 구하면서 색깔별 누적 합도 따로 구해줌. 같은 색깔 + 같은 크기일 경우에도 따로 처리. 아이디어 구상은 쉬우나 예외 처리 부분이 신경 쓸 게 많았음.
백준 BOJ 11683
문제 백준 BOJ https://www.acmicpc.net/problem/11663 11663번: 선분 위의 점 첫째 줄에 점의 개수 N과 선분의 개수 M이 주어진다. (1 ≤ N, M ≤ 100,000) 둘째 줄에는 점의 좌표가 주어진다. 두 점이 같은 좌표를 가지는 경우는 없다. 셋째 줄부터 M개의 줄에는 선분의 시작점과 www.acmicpc.net 사용 알고리즘 Binary search 풀이 n^2이면 시간 초과가 나기 때문에 brute force는 안되고 이분 탐색을 써야 한다. 선분의 왼쪽 지점은 std:: lower_bound, 오른쪽은 std::upper_bound 사용하여 index를 각각 찾은 후 차이를 구해주면 된다. 점이 선분들 범위 밖을 아예 벗어났을 때 예외 처리를 따로 해주어야..
백준 BOJ 5582 공통 부분 문자열
문제 백준 BOJ https://www.acmicpc.net/problem/5582 5582번: 공통 부분 문자열 두 문자열이 주어졌을 때, 두 문자열에 모두 포함된 가장 긴 공통 부분 문자열을 찾는 프로그램을 작성하시오. 어떤 문자열 s의 부분 문자열 t란, s에 t가 연속으로 나타나는 것을 말한다. 예를 들 www.acmicpc.net 사용 알고리즘 Dynamic programming String 풀이 2차원 DP. dp[i][j] = 첫번재 문자열 i까지, 두번째 문자열 j까지 봤을 때 최대 길이 if(s1[i]==s2[j]){ dd[i+1][j+1]=dd[i][j]+1;
백준 BOJ 20003 거스름돈이 싫어요
문제 백준 BOJ 20003 https://www.acmicpc.net/problem/20003 20003번: 거스름돈이 싫어요 프로불편러 지수는 딱 떨어지지 않는 수는 질색이다. 거스름돈이 남는 것도 딱 질색이다. 지수가 아이템을 사려 하는데, 아이템의 가격은 다 분수로 이루어져 있다. 지금은 가령, 3/2코인을 사려 www.acmicpc.net 사용 알고리즘 Mathematics Number theory Euclidean algorithm 풀이 우선 입력받은 값들을 모두 기약분수로 바꾸고 모든 분모들의 LCM을 구해 분모를 먼저 찾는다. 분모들을 LCM으로 통일시켜주면서 분자를 적절한 값을 곱해 수정한다. 분자들의 GCD를 구하면 출력해야 할 답의 분자가 된다. 답의 분자가 항상 1이 나올 것이라고 ..
백준 BOJ 1027 고층 건물
문제 백준 BOJ https://www.acmicpc.net/problem/1027 1027번: 고층 건물 세준시에는 고층 빌딩이 많다. 세준시의 서민 김지민은 가장 많은 고층 빌딩이 보이는 고층 빌딩을 찾으려고 한다. 빌딩은 총 N개가 있는데, 빌딩은 선분으로 나타낸다. i번째 빌딩 (1부터 시작) www.acmicpc.net 알고리즘 Brute force 풀이 각 건물에 대해 보이는 건물의 개수를 일일이 확인해본다. 건물 쌍 (l,r) (l
백준 BOJ 1812 사탕
문제 백준 BOJ 1812 사탕 https://www.acmicpc.net/problem/1812 1812번: 사탕 첫째 줄에 N(3≤N≤999, N은 홀수)이 주어진다. 둘째 줄부터 N개의 줄에 걸쳐 1번 학생과 2번 학생이 가지고 있는 사탕의 수의 합, 2번 학생과 3번 학생이 가지고 있는 사탕의 수의 합, …, N-1번 학생 www.acmicpc.net 풀이 항상 N이 홀수라는 점에 착안. 1~2 3~4 5~6 과 같은 식으로 더해 나가면 sum - a[n]의 값이 나온다. sum은 입력 값을 모두 더해 2로 나누면 나오므로 a[n]을 구할 수 있다. a[n]을 구했으므로 모든 값을 차례대로 구할 수 있다.