Algorithm475 [파이썬] 백준 1194: 달이 차오른다, 가자. (골드1) [파이썬] 백준 1194: 달이 차오른다, 가자. (골드1) 1194번: 달이 차오른다, 가자. 첫째 줄에 미로의 세로 크기 N과 가로 크기 M이 주어진다. (1 ≤ N, M ≤ 50) 둘째 줄부터 N개의 줄에 미로의 모양이 주어진다. 같은 타입의 열쇠가 여러 개 있을 수 있고, 문도 마찬가지이다. 그리고, www.acmicpc.net 문제 풀이 0. 방향성 생각 열쇠를 먹은 유무에 따라 문을 열수있는지 여부가 정해진다. 2D 배열이 2500, 열쇠가 6개이므로 2500*64 정도면 충분히 비트마스킹으로 가능 3D visit 배열을 만들어서 BFS로 진행 1. 입력 from collections import deque,defaultdict as dd import sys input = lambda : sy.. 2023. 12. 19. [파이썬] 백준 5719 : 거의 최단 경로 (플레5) [파이썬] 백준 5719 : 거의 최단 경로 (플레5) 5719번: 거의 최단 경로 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 장소의 수 N (2 ≤ N ≤ 500)과 도로의 수 M (1 ≤ M ≤ 104)가 주어진다. 장소는 0부터 N-1번까지 번호가 매겨져 있 www.acmicpc.net 문제 풀이 0. 방향성 생각 다익스트라를 돌려서 end node에 최소 비용으로 도달하는 경우를 찾고, 이 노드들이 어디서 오는지 체크한다. 체크를 위해서 trace 변수를 넣어서 각 node로 들어오는 node가 어떤 노드인지 기록한다. trace를 이용해서 node를 최단 경로 노드들을 모두 shortcut에 넣는다. 다익스트라를 한 번 더 돌려서 end node에 도달할 .. 2023. 12. 19. [파이썬] 백준 3089 : 네잎 클로버를 찾아서 (골드2) [파이썬] 백준 3089 : 네잎 클로버를 찾아서 (골드2) 3089번: 네잎 클로버를 찾아서 숭이는 지구에 놀러온 외계인에게 조정당하고 있다. 외계인은 숭이를 이용해서 네잎 클로버를 찾은 뒤, 숭이를 그 자리에 놔두고 다시 자기들의 행성으로 떠나려고 한다. 숭이가 있는 곳은 2차 www.acmicpc.net 문제 풀이 방향성 생각 명령이 주어진 방향에는 항상 네잎클로버가 존재한다. UD 입력이 주어지면 x좌표를 고정시키고 y좌표에 대해서 이분탐색을 진행한다. LR 입력이 주어지면 y좌표를 고정시키고 x좌표에 대해서 이분탐색을 진행한다. 숫자가 커지는 방향으로 갈 때는 bisect_right을 써서 이동하려는 인덱스 반환받아서 업데이트. 숫자가 작아지려는 방향으로 갈 때는 bisect_left를 써서 인.. 2023. 12. 18. [파이썬] 백준 5624 : 좋은 수 (골드 3) [파이썬] 백준 5624 : 좋은 수 (골드 3) 5624번: 좋은 수 정수 N개로 이루어진 수열 A가 있다. 이때, i번째 수가 그 앞에 있는 수 세 개의 합으로 나타낼 수 있을 때, 그 수를 좋다고 한다. (같은 위치에 있는 수를 여러 번 더해도 된다) 수열이 주어졌을 때 www.acmicpc.net 문제 풀이 방향성 생각 입력이 5000이라 N^2까지 가능 처음 풀이는 순회 하면서 모든 조합을 저장해서 조회하는 식으로 했는데 시간 초과 현재 숫자 a에서 이전에 arr에서 등장했던 숫자 o를 빼면 a-o가 나온다. 이 a-o가 이전에 두 숫자의 조합으로 만들 수 있으면 그 숫자을 카운팅 경우의 수가 아니라, 각 위치에 있는 숫자가 좋은 수인지만 판별하면 된다. 전체코드 n = int(input()) .. 2023. 12. 18. 이전 1 ··· 61 62 63 64 65 66 67 ··· 119 다음
