본문 바로가기
728x90

알고리즘316

[python] 백준 30677 반짝반짝 빛나는 별가루 https://www.acmicpc.net/problem/30677 30677번: 반짝반짝 빛나는 별가루 첫째 줄에는 $N,K,C,R$ 이 공백을 사이에 두고 주어진다. $(1 \leq K \leq N \leq 100 \, 000;$ $1 \leq C \leq 100;$ $1 \leq R \leq 100)$ 둘째 줄에는 $base_1, \cdots , base_K$가 공백을 사이에 두고 주어진다. $(1 \leq base_i \le www.acmicpc.net 문제해결 쉬운 문제인줄 알았는데 계속 오류가나서 많이 해매었던 문제 원인은 정밀도에 있었다고 한다. $combo*C$나 $skill_{i} s_{i}$같은 경우 소수점 계산에서 오류가 날 수 있다고 한다. 따라서 각각 100을 곱해준 다음 나중에 .. 2024. 2. 19.
[python] 백준 23258 밤편지 https://www.acmicpc.net/problem/23258 23258번: 밤편지 $C = 3$일 때, 1번 정점에서 4번 정점으로 가는 경로 중 3번 정점을 지나는 경로는 반딧불이 3번 정점에서 8방울의 이슬을 마시고 잠들어버리기 때문에 불가능하다. 따라서 가능한 경로는 2번 정점 www.acmicpc.net 문제 해결 DP의 전형적인 문제이다. 우선 $\sum_{i=1}^{i=C-1} 2^{i} k일 때에 DP[k][i][j]이면 지날 수 없다. 하지만 지날.. 2024. 2. 18.
[python] 백준 2628 종이자르기 https://www.acmicpc.net/problem/2628 2628번: 종이자르기 첫줄에는 종이의 가로와 세로의 길이가 차례로 자연수로 주어진다. 가로와 세로의 길이는 최대 100㎝이다. 둘째 줄에는 칼로 잘라야하는 점선의 개수가 주어진다. 셋째 줄부터 마지막 줄까지 한 www.acmicpc.net 문제 해결 종이를 자르고 가장 큰 넓이를 구하는 문제 자른 부분의 좌표를 가로, 세로로 나눠서 오름차순으로 정렬한 다음 반복문을 통해 가장 큰 넓이를 출력하면 되는 문제 CODE import sys input = sys.stdin.readline def solve(): result = 0 for i in range(len(width)-1): for j in range(len(height)-1): x =.. 2024. 2. 16.
[python] 백준 2527 직사각형 https://www.acmicpc.net/problem/2527 2527번: 직사각형 4개의 줄로 이루어져 있다. 각 줄에는 8개의 정수가 하나의 공백을 두고 나타나는데, 첫 4개의 정수는 첫 번째 직사각형을, 나머지 4개의 정수는 두 번째 직사각형을 각각 나타낸다. 단 입력 직사 www.acmicpc.net 문제 해결 조건을 잘 분리해서 출력하는 문제 우선 겹치지 않는 경우부터 잡는 것이 좋다. 두 직사각형 각각의 x, y의 최소 값 좌표와 최댓 값 좌표가 있는데 어떤 직사각형의 최솟값 좌표가 다른 직사각형의 최댓값 좌표보다 큰 것이 존재하면 겹칠 수 없다.(x, y 둘 중 하나라도) 만약 어떤 직사각형의 최솟값 좌표가 다른 직사각형 최댓값 좌표와 같은 것이 존재한다면 겹쳐서 선이나 점이 만들어진다... 2024. 2. 15.
728x90