본문 바로가기
728x90

알고리즘/[python] 백준 BOJ328

[python] 백준 2157 여행 https://www.acmicpc.net/problem/2157 2157번: 여행 첫째 줄에 N(1 ≤ N ≤ 300), M(2 ≤ M ≤ N), K(1 ≤ K ≤ 100,000)가 주어진다. K는 개설된 항공로의 개수이다. 다음 K개의 줄에는 각 항공로에 대한 정보를 나타내는 세 정수 a, b, c(1 ≤ a, b ≤ N, 1 ≤ c ≤ 1 www.acmicpc.net 문제 해결 처음에 다익스트라로 풀려고 했으나 k가 매우 클 수 있는 바람에 시간초과가 났다. 큰 수를 계산해야할 때는 무조건 dp가 된다! 그럼 dp를 어떻게 잡아야할까? 우선 똑같은 출발지에서 도착지점까지 항공로가 여러가지가 있을 수 있기 때문에 graph를 $ n \times n$ 행렬을 만든다음 graph[i][j]의 값읠 i에서.. 2023. 5. 7.
[python] 백준 1132 합 https://www.acmicpc.net/problem/1132 1132번: 합 N개의 수가 주어진다. 이 숫자는 모두 자연수이고, 알파벳 A부터 J가 자리수를 대신해서 쓰여 있다. 이 알파벳은 모두 한 자리를 의미한다. 그리고, 각 자리수는 정확하게 알파벳 하나이다. 0으로 www.acmicpc.net 문제 해결 알파벳에 숫자를 부여해서 주어진 문자의 합이 가장 크도록 만들기 단 한자리 알파벳이 주어졌을 때 그 알파벳은 0이 되면 안된다. 0이 안되는 알파벳을 어떻게 구현할까 고민했는데 True,False로 주어진 정보를 추가하는 수밖에 없는 것 같다. 구현은 어렵지 않다! CODE import sys input = sys.stdin.readline n = int(input()) alpha = [[0.. 2023. 5. 7.
[python] 백준 2666 벽장문의 이동 https://www.acmicpc.net/problem/2666 2666번: 벽장문의 이동 첫 번째 줄에 벽장의 개수를 나타내는 3보다 크고 20보다 작거나 같은 하나의 정수, 두 번째 줄에 초기에 열려있는 두 개의 벽장을 나타내는 두 개의 정수, 그리고 세 번째 줄에는 사용할 벽장들 www.acmicpc.net 문제 해결 재귀를 이용해 모든 경우를 해보면서 최적의 해를 출력 내 생각에는 함수 구현 문제라고 보는 겻이 편하다. CODE import sys input = sys.stdin.readline n = int(input()) first, second =map(int,input().split()) m = int(input()) orders = [] dp = [[[0 for _ in range(n+.. 2023. 5. 6.
[python] 백준 2831 댄스 파티 https://www.acmicpc.net/problem/2831 2831번: 댄스 파티 남자 N명과 여자 N명이 상근이가 주최한 댄스 파티에 왔다. 상근이는 모든 사람의 키를 알고있다. 각 남자는 모두 여자와 춤을 출 수 있고, 여자는 남자와 춤을 출 수 있다. 모든 사람은 많아야 한 www.acmicpc.net 문제 해결 음수-양수, 양수-음수만 짝이 가능하다. 음수쪽 절대값이 더 커야한다. sort()를 통해 수를 배열하고 음수인 부분이 더 클 경우에 짝을 만들어준다. 남자는 가장 작은수부터, 여자는 가장 큰 수부터 시작해서 짝을 맞춰본다.(절대값이 큰것끼리 짝을 맞춰야 더 많이 짝을 만들 수 있다.) CODE n = int(input()) M = list(map(int, input().split(.. 2023. 5. 6.
728x90