본문 바로가기
728x90
반응형

알고리즘109

[백준] 13549번: 숨바꼭질 3 - python https://www.acmicpc.net/problem/13549 13549번: 숨바꼭질 3 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 www.acmicpc.net 아이디어 BFS로 탐색을 하면서 순간이동할때는 가중치를 더하지말고, 이동할때는 더해서 dis 리스트에 계속해서 상태트리형식으로 뻗어나가는 형태를 생각하고 문제를 풀었다. 그러던중 신기한 현상이 발생했다. from collections import deque import sys input = sys.stdin.readline n, m = map(int, inpu.. 2024. 4. 12.
[백준] 12865번: 평범한 배낭 - python https://www.acmicpc.net/problem/12865 12865번: 평범한 배낭첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000)www.acmicpc.net 냅색 알고리즘 응용문제 n, m = map(int, input().split())dp = [0] * (m+1)for _ in range(n): w, v = map(int, input().split()) # 역순으로 루프를 돌며 최대 가치 계산 for j in range(m, w-1, -1): dp[j] = .. 2024. 4. 11.
[백준] 11660번: 구간 합 구하기 5 - python https://www.acmicpc.net/problem/11660 11660번: 구간 합 구하기 5 첫째 줄에 표의 크기 N과 합을 구해야 하는 횟수 M이 주어진다. (1 ≤ N ≤ 1024, 1 ≤ M ≤ 100,000) 둘째 줄부터 N개의 줄에는 표에 채워져 있는 수가 1행부터 차례대로 주어진다. 다음 M개의 줄에는 네 www.acmicpc.net 처음 아이디어 무지성 더하기를 작성.. 당연히 안된다.. import sys input = sys.stdin.readline n, m = map(int, input().split()) arr = [] for _ in range(n): arr.append(list(map(int, input().split()))) for _ in range(m): sum =.. 2024. 4. 11.
[백준] 9465번: 스티커 - python https://www.acmicpc.net/problem/9465 9465번: 스티커 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 n (1 ≤ n ≤ 100,000)이 주어진다. 다음 두 줄에는 n개의 정수가 주어지며, 각 정수는 그 위치에 해당하는 스티커의 www.acmicpc.net 아이디어 할당된 저장변수에 계속해서 최대값을 저장해나가면서 마지막에 가장 큰 값을 추출 저장하는 것은 다른 행이므로 비교를 하면서 더해나간다. import sys input = sys.stdin.readline T = int(input()) for _ in range(T): dp = [] n = int(input()) dp.append(list(map(int, input().split(.. 2024. 4. 11.
728x90
반응형

티스토리툴바