dlwocks31의 PS일기장

BOJ 24659 - Game with Balls and Boxes https://www.acmicpc.net/problem/24659 24659번: Game with Balls and Boxes Print one integer: the minimal sum of coins you need to pay to have $i$-th ball in the $i$-th box for each $i$ after two rounds. www.acmicpc.net 문제: 번호가 있는 상자와 공이 있고, 목표는 모든 공을 번호가 같은 상자에 도로 집어넣는 것이다. 두 번의 스테이지에 걸쳐 일부 박스를 연 후에 공을 옮길 수 있고, 이 때 박스를 여는 코스트를 최소화하는 것이 목표이다. 풀이: 더보기 먼저, 문제의 P ..

BOJ 16741 - Emergency Evacuation https://www.acmicpc.net/problem/16741 16741번: Emergency Evacuation The Japanese government plans to increase the number of inbound tourists to forty million in the year 2020, and sixty million in 2030. Not only increasing touristic appeal but also developing tourism infrastructure further is indispensable to accomplish su www.acmicpc.net 자동차 좌석에 사람이 앉아있고, 사람당 한 칸..

BOJ 9323 - 무임승차 https://www.acmicpc.net/problem/9323 9323번: 무임승차 벌금의 기댓값은 확인받을 확률 * 벌금 으로 계산할 수 있으며, 각 운행 경로는 독립적이므로 경로 X에서의 기댓값을 E[X], 경로 Y에서의 기댓값을 E[Y]라 할 때, X-Y 경로의 기댓값은 E[X]+E[Y]가 된다 www.acmicpc.net 기차를 탈 때 티켓 요금과 무임승차 벌금을 고려하여 출발지에서 도착지까지의 최소 기댓값을 구하는 문제. 풀이: 더보기 우선, n개의 도시를 거치는 표를 사는 것을 마치 n-1개의 독립적인 표를 사되, 첫 도시에서만 s원을 내야 하는 것처럼 생각할 수 있다. 이렇게 생각하게 되면 아래와 같은 점화식을 뽑을 수 있다. dp[i][0] = i번 노드까지..

BOJ 10792 - Ship Traffic https://www.acmicpc.net/problem/10792 10792번: Ship Traffic The first line of input contains six integers: the number of lanes n (1 ≤ n ≤ 105), the width w of each lane (1 ≤ w ≤ 1 000), the speed u of ships and the speed v of the ferry (1 ≤ u, v ≤ 100), the ferry’s earliest start time t1 and the ferry www.acmicpc.net 문제: N행의 배가 일정한 속도로 지나가고, 내 페리선이 수직 방향으로 일정한 속도로 배들 사이를 ..

HTML 삽입 미리보기할 수 없는 소스 BOJ 7420 - 맹독 방벽 (P5) 문제: 다각형이 주어졌을 때, 이 다각형에서 거리를 L이상 유지하면서 다각형을 두르는 벽의 최소 길이를 구하는 문제 풀이: 더보기 먼저, 원래 다각형을 해당 다각형의 컨벡스 헐로 바꾼다. (그렇게 해도 답이 늘어나지 않음을 관찰) 컨벡스 헐의 간선 하나마다, 해당 간선에서 L만큼의 거리를 두고 같은 길이의 벽을 새로 짓는다고 생각하자. 이제 새로 지은 벽을 이어주어야 하는데, 그렇게 지어야 하는 벽을 모두 합치면 반지름 L의 원이 된다. 따라서 답은 컨벡스 헐의 모든 간선 거리의 합 + 2* PI * L 이 된다. 코드: http://boj.kr/44f5fc68b69f45e28f33edc58256dab3 BOJ 10265 - ..

BOJ 1979 - 극적인 곱셈 (P5) https://www.acmicpc.net/problem/1979 1979번: 극적인 곱셈 첫째 줄에 구한 n-극적인 숫자 중 마지막 숫자가 k인 수를 출력한다. 그런 숫자가 존재하지 않는 경우에는 0을 출력한다. www.acmicpc.net 문제: n을 곱했을 때 오른쪽으로 숫자가 한 칸씩 옮겨진 수가 되는 수를 n-극적인 수라고 부른다. n-극적이면서 마지막 숫자가 k인 수를 찾는 문제다. 풀이: 더보기 우선, n = 1일 때는 답이 k이다. 이 부분을 먼저 처리한다. k가 마지막 자리에 있는 n-극적인 숫자는, n을 곱한 후에는 k가 첫 번째 자리로 가고, 나머지 숫자들은 자리만 한 칸씩 이동한다. k를 제외하고 나머지 숫자들로 이루어진 수를 x라고 생각해보..

BOJ 6757 - 팰린드롬 진법 https://www.acmicpc.net/problem/6757 6757번: 팰린드롬 진법 첫째 줄에 X가 주어진다. (2 ≤ X ≤ 1,000,000,000) www.acmicpc.net 문제: 10진법 숫자 X가 주어졌을 때, b진법으로 나타냈을 때, 팰린드롬인 것의 개수를 구하자. (2 ≤ b

BOJ 13308 - 주유소 (P5) https://www.acmicpc.net/problem/13308 13308번: 주유소 표준 입력으로 다음 정보가 주어진다. 첫 번째 줄에는 도시의 수와 도로의 수를 나타내는 정수 N(2 ≤ N ≤ 2,500)과 정수 M(1 ≤ M ≤ 4,000)이 주어진다. 다음 줄에 각 도시 주유소의 리터당 가격이 도 www.acmicpc.net 문제: N개의 도시와 M개의 도로가 있고, 각 도시에는 주유소가 있다. 1번 도시에서 출발해 N번 도시로 갈려고 하는데, 차의 기름통은 무한하다. 1km마다 1리터의 기름을 필요로 하고, 각 도시의 리터당 기름 가격이 주어지고, 도로의 길이가 주어질 때, 최소 비용을 계산하자. 풀이: 더보기 풀이 1 각 도시에서 다른 모든 도시로 나가..