본문 바로가기
728x90

백준41

[BOJ/Python] 1520. 내리막 길 📌 문제 https://www.acmicpc.net/problem/1520 1520번: 내리막 길 첫째 줄에는 지도의 세로의 크기 M과 가로의 크기 N이 빈칸을 사이에 두고 주어진다. 이어 다음 M개 줄에 걸쳐 한 줄에 N개씩 위에서부터 차례로 각 지점의 높이가 빈 칸을 사이에 두고 주어진다. www.acmicpc.net 📌 문제 접근 방법 이것저것 내 생각으로 할 수 있는 모든 시도를 다 해본 것 같다! (그냥 dfs, 방문 체크 리스트를 아예 가지고 다니기 등등) 결국 포기하고 구글링..! dp를 활용해야 하는 문제였다. 출발점에서 시작해서 도착점까지 도달할 수 있다면, dp 리스트에 값을 + 해준다. 이를 다 체크하면, (0, 0)에는 출발점에서 도착점까지 갈 수 있는 경우의 수가 남는다. 📌 코드.. 2021. 10. 4.
[BOJ/Python] 2960. 에라토스테네스의 체 📌 문제 https://www.acmicpc.net/problem/2960 2960번: 에라토스테네스의 체 2, 4, 6, 8, 10, 3, 9, 5, 7 순서대로 지워진다. 7번째 지워진 수는 9이다. www.acmicpc.net 📌 문제 접근 방법 2부터 N까지의 숫자 리스트를 생성한다. 가장 작은 수가 소수라면 그 수의 배수를 모두 리스트에서 제거한다. (나중에 생각하고 알게 된 점이지만, 어차피 가장 작은 수는 항상 소수이므로 소수판별을 생략해도 된다.) 📌 코드 def is_prime(number): for i in range(2, number): if not number%i: return False else: return True N, K = map(int, input().split()) nu.. 2021. 10. 4.
[BOJ/Python] 1600. 말이 되고픈 원숭이 📌 문제 https://www.acmicpc.net/problem/1600 1600번: 말이 되고픈 원숭이 첫째 줄에 정수 K가 주어진다. 둘째 줄에 격자판의 가로길이 W, 세로길이 H가 주어진다. 그 다음 H줄에 걸쳐 W개의 숫자가 주어지는데, 0은 아무것도 없는 평지, 1은 장애물을 뜻한다. 장애물이 있 www.acmicpc.net 📌 문제 접근 방법 말처럼 움직일 경우와 보통으로 움직일 경우의 델타 배열을 따로 정의 visited를 3차원으로 만들어서 말처럼 움직인 횟수를 인덱스로 각각 다른 리스트에 방문 체크 📌 코드 from collections import deque def bfs(i, j): queue = deque() queue.append((i, j, 0)) visited = [[[0 f.. 2021. 10. 4.
[BOJ/Python] 12865. 평범한 배낭 📌 문제 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 📌 문제 접근 방법 처음에는 가치가 큰 물건 별로 우선적으로 배낭에 넣는 방식으로 구현해보았으나 시간초과! 결국 구글링을 해보니 Knapsack Algorithm을 사용해야 하는 것이었다. 인덱스 에러가 나지 않도록 0번째 줄을 포함해서 2차원 배열을 생성한다. i 번째 물건을 가방에 넣었을 때 / 넣지 않았을 때의 최대 .. 2021. 10. 4.
728x90

티스토리툴바