본문 바로가기
728x90

알고리즘/[python] 백준 BOJ328

[python] 백준 1064 평행사변형 https://www.acmicpc.net/problem/1064 1064번: 평행사변형 평행사변형은 평행한 두 변을 가진 사각형이다. 세 개의 서로 다른 점이 주어진다. A(xA,yA), B(xB,yB), C(xC,yC) 이때, 적절히 점 D를 찾아서 네 점으로 평행사변형을 만들면 된다. 이때, D가 여러 개 나 www.acmicpc.net 문제 해결 3 점이 주어졌고 어떻게 연결하느냐에 따라 평행사변형 모양이 달라질 수 있다. 점 a, b, c가 있다고 하면 abc 연결과 acb연결은 다르다 만약 점이 일직선으로 있다면 평행사변형을 만들 수 없다. 따라서 그 경우는 -1.0을 출력하고 나머지 경우는 여러가지 연결을 해보고 가장 짧은 선분 합과 가장 긴 선분 합 차를 구하고 2배를 해주면 된다. 주의할.. 2024. 2. 21.
[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.
728x90