본문 바로가기

PS/BOJ57

백준 1234 / C++ https://www.acmicpc.net/problem/1234 1234번: 크리스마스 트리 첫째 줄에 트리의 크기 N, 빨강의 개수, 초록의 개수, 파랑의 개수가 주어진다. N은 10보다 작거나 같다. 빨강, 초록, 파랑의 개수는 0보다 크거나 같고, 100보다 작거나 같다. www.acmicpc.net [ 풀이 ] dp[h][r][g][b]를 h높이를 채울 것이고 지금까지 r, g,b만큼 색상을 쓴 경우의 수라고 하자. 상태전이는 다음과 같다. 1. 한 색으로 h칸을 모두 칠한다. : dp[h+1][r+h][g][b] 로 전이 (g, b도 마찬가지) 2. h가 짝수면 두개를 골라 절반씩 칠한다. : dp[h+1][r+h/2][g+h/2][b] * h!/(h/2)!(h/2)! 로 전이 (g, b도 마.. 2022. 8. 8.
백준 25315 / C++ https://www.acmicpc.net/problem/25315 25315번: N수매화검법 화산파의 장로 우경은 새로운 무공 N수매화검법을 창안했다. N수매화검법은 이십사수매화검법을 발전시킨 검법으로 총 $N$개의 베기(검으로 무언가를 베는 동작)로 이루어진다. N수매화검법은 2 www.acmicpc.net [ 풀이 ] 선분교차여부는 CCW로 잘 구해주면 된다. 이제 (m+1)*w[i] 이 부분을 처리해야 한다. 서로 교차하는 것끼리 묶었다고 해보자. 묶은 것들은 m이 최대부터 시작하게 된다. (안벤 베기의 개수니까) 벤 후엔 계속 m은 감소하므로 따라서 묶은것들은 가중치가 작은것부터 처리해야 값이 최소가 된다. (그리디하게 최소는 최대와, 최대는 최소와 만나야 곱들의 합이 최소가 됨) 이제 구현해보.. 2022. 8. 8.
백준 14908 / C++ https://www.acmicpc.net/problem/14908 14908번: 구두 수선공 최소 보상금을 지불하는 작업 순서를 출력해야 한다. 모든 작업은 입력에서의 번호(1~N)로 표시해야 한다. 모든 정수는 한 줄로 표시해야 하며, 각 작업은 공백 문자로 구분한다. 여러 가지 해답 www.acmicpc.net [ 풀이 ] (T1 S1) (T2 S2) ... (Tn Sn) 이 최적해라고 가정하자. 이제 (T1 S1) (T2 S2)를 교환했을 때 값을 구해서 비교하자. 양식의 차를 비교하면 1식-2식 = T1S2-T2S1이 되고 최적해조건에 따라 T1S2 < T2S1을 만족해야 한다. 즉, T1/S1 < T2/S2 이다. 중간에 있는 (Ti Si)와 (Ti+1, Si+1)을 교환했을 때도 다 소거되고.. 2022. 8. 5.
백준 10277 / C++ https://www.acmicpc.net/problem/10277 10277번: JuQueen The input contains a single test case. It starts with a line containing three integers C, N, and O, where C is the number of cores (1 ≤ C ≤ 4 587 520) to manage, N is the number of frequency steps for each core (1 ≤ N ≤ 10 000) and O is the number www.acmicpc.net [ 풀이 ] 문제조건이 특이하다. 값을 변경시킬때마다 증가하거나 감소시키는데 하나라도 0이나 N이 되면 변경행위를 멈춘다. 예를 들어 2 3 3.. 2022. 8. 5.

티스토리툴바