알고리즘60 [Python] 백준 1082: 방 번호 https://www.acmicpc.net/problem/1082 1082번: 방 번호 스타트링크가 입주한 사무실은 방 번호를 직접 정할 수 있다. 방 번호를 정하려면 1층 문방구에서 파는 숫자를 구매해야 한다. 숫자를 구매하기 위해 준비한 금액은 M원이고, M원을 모두 사용해 www.acmicpc.net 1. 가장 큰 방 번호를 출력하므로 뒤에서부터 dp를 시작한다. 2. 현재 값, 현재 인덱스 값(현재 dp가 무한일 수도 있기 때문), 전의 값 * 10 + 현재 값 중 가장 큰 값을 넣는다. INF = 5001 n = int(input()) room = list(map(int, input().split())) m = int(input()) dp = [-INF for _ in range(m+1)] fo.. 2021. 9. 25. [Python] 백준 1083: 소트 https://www.acmicpc.net/problem/1083 1083번: 소트 크기가 N인 배열 A가 있다. 배열에 있는 모든 수는 서로 다르다. 이 배열을 소트할 때, 연속된 두 개의 원소만 교환할 수 있다. 그리고, 교환은 많아봐야 S번 할 수 있다. 이때, 소트한 결과가 사전 www.acmicpc.net 1. 사전 반대 순이라는 말은 리스트를 큰 순서대로 나열하는 것이다. 2. 현재 인덱스를 기준으로 뒤에 가장 큰 값을 비교한다. 3. 남은 횟수가 더이상 없으면 종료한다. S는 1000000보다 작거나 같은 음이 아닌 정수이다.라는 조건이 있는데 이 조건은 횟수가 0일 수도 있다는 것이다. 이것 때문에 틀렸다가 바로 정정했다. n = int(input()) lst = list(map(int, .. 2021. 9. 25. [Python] 백준 1700: 멀티탭 스케쥴링 https://www.acmicpc.net/problem/1700 1700번: 멀티탭 스케줄링 기숙사에서 살고 있는 준규는 한 개의 멀티탭을 이용하고 있다. 준규는 키보드, 헤어드라이기, 핸드폰 충전기, 디지털 카메라 충전기 등 여러 개의 전기용품을 사용하면서 어쩔 수 없이 각종 전 www.acmicpc.net 1. 현재 멀티탭에 삽입하고자 하는 플러그가 있으면 continue 한다. 2. 멀티탭 자리가 비어있으면 그대로 꽂는다. 3. 멀티탭의 자리가 꽉 찼을 경우 (이 경우를 찾는 게 너무 어려웠다.) 현재 멀티탭에 있는 정보중 나중에 꽂을 플러그가 멀어지면 멀어질수록 뽑아야 할 우선순위가 높다. n, k = map(int, input().split()) items = list(map(int, inpu.. 2021. 9. 19. [Python] 백준 1916: 최소비용 구하기 https://www.acmicpc.net/problem/1916 1916번: 최소비용 구하기 첫째 줄에 도시의 개수 N(1 ≤ N ≤ 1,000)이 주어지고 둘째 줄에는 버스의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 M+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 www.acmicpc.net 1. 다익스트라 알고리즘을 이용한다. 2. 시작정점에서 모든 정점 방문후, 시작정점에서 각 정점마다 가장 짧은 비용을 출력한다. 3. 두 정점간의 여러가지 경로값이 주어질수도 있다. 그래서 매 경로마다 최솟값을 갱신해줘야한다. 아래는 배열을 이용한 다익스트라 알고리즘인데 정점마다 모든정점을 확인해야하기 때문에 O(V^2) 시간이 드는데 이는 정점이 많고 간선이 적.. 2021. 9. 17. 이전 1 ··· 8 9 10 11 12 13 14 15 다음