PS87 백준 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. 백준 3172 / C++ https://www.acmicpc.net/problem/3172 3172번: 현주와 윤주의 재미있는 단어 게임 현주와 윤주는 일요일마다 재미있는 단어 게임을 하면서 시간을 보낸다. 단어 게임을 하던 중, 두 사람은 서로 좋아하지 않는 단어가 있다는 사실을 알게 되었다. 두 단어 A와 B가 있을 때, A가 B www.acmicpc.net [ 풀이 ] 문자열을 우선 정렬해놓자. 이제 정렬후 인덱스로만 보면 처음 문자열의 사전순을 알 수 있다. 이 인덱스를 문자열과 함께 묶어서 들고다니자. 이제 정렬한 문자열을 모두 뒤집는다. 뒤집고 다시 정렬한다. 이제 순회를 시작해보자. 순회의 방향은 항상 뒤집은 문자열이 앞서는 순으로 진행된다. 그럼 좋아하지 않는 순서쌍이 되려면 다음에 보는 문자열의 인덱스가 현재보는.. 2022. 8. 4. 백준 1086 / C++ https://www.acmicpc.net/problem/1086 1086번: 박성원 첫째 줄에 정답을 기약분수 형태로 출력한다. p/q꼴로 출력하며, p는 분자, q는 분모이다. 정답이 0인 경우는 0/1로, 1인 경우는 1/1로 출력한다. www.acmicpc.net [ 풀이 ] N이 작고 순열의 각 원소의 순서가 중요하므로 비트DP로 순회하자. p1 p2 .... pn 순으로 간다고 하자. p1에서 p2로 갈 때 수는 p1*10^(p2의 길이)+p2 가 된다. p2의 길이는 최대 50이므로 단순 계산으론 안되고 미리 10^m (modk)를 전처리해놓으면 된다. p_i들 또한 k로 나눈 나머지만 중요하므로 순회하면서 모두 k로 나눈 나머지로 전처리해놓자. 이제 dp식을 세우자. dp[bit][v]는 .. 2022. 8. 4. 이전 1 ··· 12 13 14 15 16 17 18 ··· 22 다음