DevYoon

link 🔗 https://www.acmicpc.net/problem/9328 9328번: 열쇠 상근이는 1층 빌딩에 침입해 매우 중요한 문서를 훔쳐오려고 한다. 상근이가 가지고 있는 평면도에는 문서의 위치가 모두 나타나 있다. 빌딩의 문은 모두 잠겨있기 때문에, 문을 열려면 열쇠가 www.acmicpc.net 📌 주의할 점 - 상근이는 빌딩 가장자리의 벽이 아닌 곳을 통해 빌딩 안팎을 드나들 수 있는데, 문제에서 주어지는 빌딩을 .으로 감싸 들어갈 입구를 마련해주었다. - 열쇠를 주웠으면 이제껏 가지 못했던 곳을 갈 수 있으므로 (문을 열어서) visit배열을 초기화해준다. 🖥️ Pypy3 통과 import sys from collections import deque input = sys.stdin.r..

link 🔗 https://www.acmicpc.net/problem/21610 21610번: 마법사 상어와 비바라기 마법사 상어는 파이어볼, 토네이도, 파이어스톰, 물복사버그 마법을 할 수 있다. 오늘 새로 배운 마법은 비바라기이다. 비바라기를 시전하면 하늘에 비구름을 만들 수 있다. 오늘은 비바라기 www.acmicpc.net ✏️ 구름이 이동할 땐 첫번째 행,열과 마지막 행,열이 연결되어 있지만 대각선에 바구니를 확인할 땐 연결되어 있지 않다는 것을 잘 생각해야 하는 문제였다. ✏️ 처음 푼 코드로는 시간초과가 났다. 구름이 사라진 칸인지 확인하는 과정에서 not in을 썼는데, 이를 배열을 하나 만들어 체크해주는 식으로 바꾸어 시간초과를 해결했다. 📌 시간초과 난 코드 import sys inpu..

link 🔗 https://www.acmicpc.net/problem/1806 1806번: 부분합 첫째 줄에 N (10 ≤ N < 100,000)과 S (0 < S ≤ 100,000,000)가 주어진다. 둘째 줄에는 수열이 주어진다. 수열의 각 원소는 공백으로 구분되어져 있으며, 10,000이하의 자연수이다. www.acmicpc.net 📌 투포인터를 사용하여 부분합을 구해주는 문제였다. 📌 sum이 S보다 크거나 같으면 어디까지 길이를 줄일 수 있는지 확인하고 📌 sum이 S보다 작으면 e를 늘려 더해준다. import sys N, S = map(int, sys.stdin.readline().split()) seq = list(map(int, sys.stdin.readline().split())) s,..

link 🔗 https://www.acmicpc.net/problem/16434 16434번: 드래곤 앤 던전 첫 번째 줄에 방의 개수 N (1 ≤ N ≤ 123,456) 과 용사의 초기 공격력 HATK (1 ≤ HATK ≤ 1,000,000) 가 주어집니다. i+1번째 줄엔 i번째 방의 정보를 나타내는 세개의 정수 ti, ai, hi (ti ∈ {1, 2}, 1 www.acmicpc.net 📌 몬스터 방일 경우와 포션 방일 경우를 나누어 생각해보았다. 📌 몬스터 방일 경우, 용사가 n번 공격하면 드래곤은 n-1번 공격한다는 점에서 착안하여 1️⃣ 몬스터의 생명력이 용사의 공격력으로 딱 나누어질 때는 1을 빼준다 2️⃣ 몬스터의 생명력이 용사의 공격력으로 딱 나누어지지 않을 때는 1을 빼주지 않는다. 📌..

link 🔗 https://www.acmicpc.net/problem/14499 14499번: 주사위 굴리기 첫째 줄에 지도의 세로 크기 N, 가로 크기 M (1 ≤ N, M ≤ 20), 주사위를 놓은 곳의 좌표 x, y(0 ≤ x ≤ N-1, 0 ≤ y ≤ M-1), 그리고 명령의 개수 K (1 ≤ K ≤ 1,000)가 주어진다. 둘째 줄부터 N개의 줄에 지 www.acmicpc.net ✏️ 단순 구현 문제! ✏️ 주사위를 굴렸을 때 어떻게 변화하는지만 찾으면 금방 해결할 수 있는 문제였다. def change(dir): # 주사위 굴렸을 때의 위치 변화 if dir == 1: dice[0], dice[2], dice[3], dice[5] = dice[3], dice[0], dice[5], dice[2..

link 🔗 https://www.acmicpc.net/problem/16234 16234번: 인구 이동 N×N크기의 땅이 있고, 땅은 1×1개의 칸으로 나누어져 있다. 각각의 땅에는 나라가 하나씩 존재하며, r행 c열에 있는 나라에는 A[r][c]명이 살고 있다. 인접한 나라 사이에는 국경선이 존재한다. 모 www.acmicpc.net ✏️ 국경을 서로 공유하는 국가를 어떻게 처리해야 할지 고민하다가 리스트에 따로 담아주었다 (deque에서는 pop을 하니까) ✏️ union(국경 공유 국가 담아주는 곳)을 처음엔 set으로 했는데, 80% 쯤에서 시간 초과가 나서 list로 바꿔주었다. ✏️ 딴에는 중복 방지하겠다고 set을 쓴 거였는데, 생각해보니 set을 쓰지 않아도 중복값이 들어갈 일이 없었다...

link 🔗 https://www.acmicpc.net/problem/1261 1261번: 알고스팟 첫째 줄에 미로의 크기를 나타내는 가로 크기 M, 세로 크기 N (1 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 미로의 상태를 나타내는 숫자 0과 1이 주어진다. 0은 빈 방을 의미하고, 1은 벽을 의미 www.acmicpc.net 🔥 BFS 🔥 visit 배열에 벽을 부순 횟수를 기록하며 BFS를 돌린다. 🔥 벽을 부숴야 할 경우 +1, 벽을 부수지 않아도 되는 경우 현재 위치의 횟수를 그대로 가져가고, appendleft로 맨 앞에 넣어준다. from collections import deque X, Y = map(int, input().split()) board = [list(map(i..

link 🔗 https://www.acmicpc.net/problem/1504 1504번: 특정한 최단 경로 첫째 줄에 정점의 개수 N과 간선의 개수 E가 주어진다. (2 ≤ N ≤ 800, 0 ≤ E ≤ 200,000) 둘째 줄부터 E개의 줄에 걸쳐서 세 개의 정수 a, b, c가 주어지는데, a번 정점에서 b번 정점까지 양방향 길이 존 www.acmicpc.net 🔥 주어진 두 정점을 반드시 통과해야 하므로 다음과 같이 두 경우로 나누어 계산하였다. 🔥 시작점 ➡️ 정점 1 ➡️ 정점 2 ➡️ 끝점 🔥 시작점 ➡️ 정점 2 ➡️ 정점 1 ➡️ 끝점 🔥 두 경우 중 가장 작은 값이 정답! import heapq import sys N, E = map(int, sys.stdin.readline().spl..

link 🔗 https://www.acmicpc.net/problem/1753 1753번: 최단경로 첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1 ≤ V ≤ 20,000, 1 ≤ E ≤ 300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 K(1 ≤ K ≤ V)가 www.acmicpc.net 🔥 기본적인 다익스트라 문제인 것 같다 import heapq import sys V, E = map(int, sys.stdin.readline().split()) snum = int(sys.stdin.readline()) board = [[] for _ in range(V+1)] result = [2e18]*(V+1) def dijkstra(st..

link 🔗 https://www.acmicpc.net/problem/18352 18352번: 특정 거리의 도시 찾기 첫째 줄에 도시의 개수 N, 도로의 개수 M, 거리 정보 K, 출발 도시의 번호 X가 주어진다. (2 ≤ N ≤ 300,000, 1 ≤ M ≤ 1,000,000, 1 ≤ K ≤ 300,000, 1 ≤ X ≤ N) 둘째 줄부터 M개의 줄에 걸쳐서 두 개 www.acmicpc.net 🔥 기본적인 다익스트라 문제 🔥 다익스트라일까 데이크스트라일까... 뭐가 맞는 것일까... import heapq import sys N, M, K, X = map(int, sys.stdin.readline().split()) inf = 2e18 board = [[] for _ in range(N+1)] resu..