생각 생각

https://acmicpc.net/problem/17472 17472번: 다리 만들기 2 첫째 줄에 지도의 세로 크기 N과 가로 크기 M이 주어진다. 둘째 줄부터 N개의 줄에 지도의 정보가 주어진다. 각 줄은 M개의 수로 이루어져 있으며, 수는 0 또는 1이다. 0은 바다, 1은 땅을 의미한다. www.acmicpc.net 삼성 A형 기출. 삼성답게 꽤나 빡구현으로 나왔다. 다만 막상 구현하면 결국 간단한 MST. import sys,heapq input=sys.stdin.readline N,M=map(int,input().split()) graph=[list(map(int,input().split())) for _ in range(N)] visited=[[False for _ in range(M)] ..

https://acmicpc.net/problem/9328 9328번: 열쇠 상근이는 1층 빌딩에 침입해 매우 중요한 문서를 훔쳐오려고 한다. 상근이가 가지고 있는 평면도에는 문서의 위치가 모두 나타나 있다. 빌딩의 문은 모두 잠겨있기 때문에, 문을 열려면 열쇠가 www.acmicpc.net 오랫동안 미뤄두던 문제인데, 풀이 방법이 떠올라서 풀게 되었다. #9328 열쇠 #최대 크기 100*100 최대 테케 100개 - 최대 1000000번 탐색 #시간복잡도 넉넉 #가능할 때까지 flood-fill. 벽 만나면 문 열고 안에 floodfill, key 줍기. #대문자: 65~90 소문자: 97~122 import sys,copy input=sys.stdin.readline def check_entranc..

https://acmicpc.net/problem/2887 2887번: 행성 터널 첫째 줄에 행성의 개수 N이 주어진다. (1 ≤ N ≤ 100,000) 다음 N개 줄에는 각 행성의 x, y, z좌표가 주어진다. 좌표는 -109보다 크거나 같고, 109보다 작거나 같은 정수이다. 한 위치에 행성이 두 개 이 www.acmicpc.net 프림으로 풀었다. 이제는 플5도 1트클이 가능해졌다. import sys from heapq import heappush, heappop input=sys.stdin.readline n = int(input()) xheap, yheap, zheap = [], [], [] # x, y, z축 각각 heap 하나씩 만들어두기 graph = [[] * n for _ in ran..

https://acmicpc.net/problem/19236 19236번: 청소년 상어 첫째 줄부터 4개의 줄에 각 칸의 들어있는 물고기의 정보가 1번 행부터 순서대로 주어진다. 물고기의 정보는 두 정수 ai, bi로 이루어져 있고, ai는 물고기의 번호, bi는 방향을 의미한다. 방향 bi는 www.acmicpc.net import sys,copy input=sys.stdin.readline graph=[[None]*4 for _ in range(4)] dirs={1:(-1,0),2:(-1,-1),3:(0,-1),4:(1,-1),5:(1,0),6:(1,1),7:(0,1),8:(-1,1)} # 방향들 미리 입력해두기 for i in range(4): temp=list(map(int,input().spli..

https://acmicpc.net/problem/7453 7453번: 합이 0인 네 정수 첫째 줄에 배열의 크기 n (1 ≤ n ≤ 4000)이 주어진다. 다음 n개 줄에는 A, B, C, D에 포함되는 정수가 공백으로 구분되어져서 주어진다. 배열에 들어있는 정수의 절댓값은 최대 228이다. www.acmicpc.net 이렇게 푸는 문제가 아닌 것 같은데, 이렇게 풀었다. import sys input=sys.stdin.readline n = int(input()) al, bl, cl, dl = [], [], [], [] ab= dict() # ab의 합을 저장해둘 딕셔너리. ans=0 for _ in range(n): a, b, c, d = map(int, input().split()) al.appe..

https://acmicpc.net/problem/21609 21609번: 상어 중학교 상어 중학교의 코딩 동아리에서 게임을 만들었다. 이 게임은 크기가 N×N인 격자에서 진행되고, 초기에 격자의 모든 칸에는 블록이 하나씩 들어있고, 블록은 검은색 블록, 무지개 블록, 일반 블록 www.acmicpc.net 시험 전 마지막 빡구현 문제. import sys input=sys.stdin.readline N,M=map(int,input().split()) graph=[list(map(int,input().split())) for _ in range(N)] dy,dx=[1,-1,0,0],[0,0,1,-1] answer=0 def find_group(): # 최대 그룹을 찾는 함수를 만들어두기 global an..

https://acmicpc.net/problem/27931 27931번: Parity Constraint Closest Pair (Easy) 첫 번째 줄에 서로 다른 두 점의 거리 중 짝수인 최솟값과 서로 다른 두 점의 거리 중 홀수인 최솟값을 공백으로 구분하여 출력한다. 단, 해당하는 거리가 없는 경우 -1을 출력한다. www.acmicpc.net 홀짝 제약이라는 알고리즘 분류가 있다는 것을 처음 알았다. 결국은 그냥 그리디하게 풀면 어렵지 않게 해결되는 문제. import sys input=sys.stdin.readline n=int(input()) lis=list(map(int,input().split())) lis.sort() # sorted되어 있다는 말은 없었으니 sort하기 INF=2*10..

https://acmicpc.net/problem/1135 1135번: 뉴스 전하기 민식이는 회사의 매니저이다. 그리고, 민식이는 회사의 중요한 뉴스를 모든 직원에게 빠르게 전달하려고 한다. 민식이의 회사는 트리 구조이다. 모든 직원은 정확하게 한 명의 직속 상사가 있다 www.acmicpc.net 처음 보는 유형. 트리에서도 dp를 시행할 수 있다는 것이 신기했다. 직관적인 풀이이긴 했는데, 구현이 헷갈렸다. import sys input=sys.stdin.readline n=int(input()) people=list(map(int,input().split())) tree=[[] for _ in range(n+1)] dp=[0 for _ in range(n+1)] # dp에는 도달하기까지 걸리는 시간..