본문 바로가기
728x90

알고리즘316

[python] 백준 5615 아파트 임대 https://www.acmicpc.net/problem/5615 5615번: 아파트 임대 첫째 줄에 아파트의 면적의 수 N이 주어진다. 다음 줄부터 N개 줄에 카탈로그에 적혀있는 순서대로 면적이 주어진다. N은 100,000이하이고 면적은 231-1이하인 양의 정수이다. www.acmicpc.net 문제해결 2xy+x+y로 무엇을 할 수 있을지 생각하면 아무것도 할 수 없다.(1차 고비) 인수분해를 해야할 것 같은데 S = 2xy+x+y라 할 때 2S+1 = (2x+1)(2y+1)로 인수분해 할 수 있다. 2S+1은 두 홀 수의 곱으로 나타낼 수 있는 것이다. 그럼 이것을 왜 하는 것인가? 바로 2S+1이 소수인지 판별해서 S를 판별하면 되는 것이다. 2S+1이 소수인지 판별하는 것은 밀러-라빈 소수 .. 2023. 7. 31.
[python] 백준 1431 시리얼 번호 https://www.acmicpc.net/problem/1431 1431번: 시리얼 번호 첫째 줄에 기타의 개수 N이 주어진다. N은 50보다 작거나 같다. 둘째 줄부터 N개의 줄에 시리얼 번호가 하나씩 주어진다. 시리얼 번호의 길이는 최대 50이고, 알파벳 대문자 또는 숫자로만 이루어 www.acmicpc.net 문제 해결 정렬 순서를 문제에 맞게 정리해서 정렬하면 되는 문제 문제는 문자열 길이, 문자열 안의 숫자의 합, 문자열 사전 순 (모두 오름차순)으로 정렬하기를 원하니 그 순서대로 리스트를 정렬해서 문자열만 출력하면 된다. CODE n = int(input()) X = [] for _ in range(n): string = str(input().rstrip()) num = len(string).. 2023. 7. 11.
[python] 백준 21610 마법사 상어와 비바라기 https://www.acmicpc.net/problem/21610 21610번: 마법사 상어와 비바라기 마법사 상어는 파이어볼, 토네이도, 파이어스톰, 물복사버그 마법을 할 수 있다. 오늘 새로 배운 마법은 비바라기이다. 비바라기를 시전하면 하늘에 비구름을 만들 수 있다. 오늘은 비바라기 www.acmicpc.net 문제 해결 순서대로 구현하면 어렵지 않은 문제 구름의 좌표를 모은 다음 주어진 방향, 주어진 크기만큼 이동해서 비를 +1씩 내려준다. 이 때 동시에 일어나도 모두 같은방향, 같은 크기만큼 가기 때문에 구름이 겹칠 일이 없다. 비가 내린 곳에서는 물복사를 할 거기 때문에 좌표를 리스트를 만들어 저장한다. 구름은 이제 모두 없고 물복사 할 곳 좌표에 차례대로 물복사를 한다. 이 때는 동시에 일.. 2023. 7. 9.
[python] 백준 2159 케익 배달 https://www.acmicpc.net/problem/2159 2159번: 케익 배달 첫째 줄에 N이 주어지고 둘째 줄에는 선아가 일하는 레스토랑의 위치가, 셋째 줄부터는 N명의 위치가 X와 Y로 주어진다. 두 좌표 사이에는 공백이 하나 이상 있다. (1 ≤ N, X, Y ≤ 100,000) www.acmicpc.net 문제 해결 케익을 받는 순서는 정해져 있다. 케익을 받을 수 있는 위치는 모두 4가지이다. 그래서 출발점-도착점에 따른 최소거리를 각각 구해야한다. 받는 위치가 다르면 다음 순서에 영향을 줄 수 있기 때문 이를 구현하기 위해 가장 좋은 것은 DP이다. dist[i][j] 는 i번째 사람 케익을 받을 때 동(j=0),서(j=1),남(j=2),북(j=3),(아래 코드는 +중앙(j=4))에.. 2023. 7. 7.
728x90