백준 18870 좌표 압축 (파이썬, 자바)
2022. 11. 1. 20:47
백준
풀이 (파이썬) import sys; import collections N = int(sys.stdin.readline()) nums = list(map(int, sys.stdin.readline().strip().split())) new_nums = list(set(nums)) new_nums.sort() graph = collections.defaultdict(int) for i in range(len(new_nums)): graph[new_nums[i]] = i for num in nums: print(graph[num], end=' ') 풀이 (자바) import java.io.*; import java.util.*; public class Main { public static void main(..
백준 1874 스택 수열 (파이썬)
2022. 10. 28. 15:17
백준
풀이 및 해설(주석) import sys def solve(): # 임시로 넣어줄 숫자들 (여기서 pop할 거임) nums = [] # +, -를 넣어줄 결과 (리턴할 거임) rst = [] # 확인해야할 인덱스를 나타냄 now = 0 for i in range(1, N+1): nums.append(i) rst.append('+') while True: if not nums: break if nums[-1] == target[now]: nums.pop() now += 1 rst.append('-') elif now >= N: break else: break # now가 N이 아니면 수열을 만들지 못하는 상황임 if now != N: return 'NO' return rst N = int(sys.stdin..
백준 9020 골드바흐의 추측 (파이썬)
2022. 10. 23. 20:55
백준
풀이 import sys; import math # 소수인지 판별하는 함수 def is_prime(x): for i in range(2, int(math.sqrt(x) + 1)): if x % i == 0: return False return True for tc in range(int(sys.stdin.readline())): N = int(sys.stdin.readline()) # 효율적으로 답을 찾기위해 반으로 나누어 left와 right로 나누어 판별 left = N//2 right = N - left rst = [0, 0] while left > 0: if is_prime(left) and is_prime(right): print(left, right) break left -= 1 right +..
백준 1149 RGB거리 (파이썬)
2022. 10. 23. 18:58
백준
풀이 import sys N = int(sys.stdin.readline()) arr = [list(map(int, sys.stdin.readline().strip().split())) for _ in range(N)] for i in range(1, N): arr[i][0] = min(arr[i-1][1], arr[i-1][2]) + arr[i][0] arr[i][1] = min(arr[i-1][0], arr[i-1][2]) + arr[i][1] arr[i][2] = min(arr[i-1][1], arr[i-1][0]) + arr[i][2] rst = 9e9 for j in range(3): rst = min(rst, arr[N-1][j]) print(rst) 후기 백트래킹 문제인줄 알고 백트래킹으로 ..
백준 2304 창고 다각형 (파이썬)
2022. 10. 20. 21:44
백준
풀이 and 해설(주석) import sys N = int(sys.stdin.readline()) max_hei = 0 max_idx = 0 len_info = 0 # 기둥의 최대 수는 1000, 입력되는 위치에 기둥을 추가 할 것 record = [0] * 1001 for _ in range(N): p, h = map(int, sys.stdin.readline().strip().split()) # 가장 높은 기둥을 중심으로 양쪽에서 접근 할 것이므로 가장 높은 기둥의 위치 정보가 필요함 if h > max_hei: max_hei = h max_idx = p # 마지막 기둥이 있는 위치 len_info = max(len_info, p) record[p] = h rst = 0 tmp = 0 # 첫 위치부터..
백준 2644 촌수계산 (파이썬)
2022. 10. 18. 20:56
백준
풀이 및 해설(주석) import sys # dfs탐색, 순회하며 cnt를 증가, p2를 만나면 cnt를 rst에 저장하고 return def solve(v, cnt): global visit, rst if v == p2: rst = cnt return visit.add(v) for u in G[v]: if u not in visit: solve(u, cnt+1) N = int(sys.stdin.readline().strip()) p1, p2 = map(int, sys.stdin.readline().strip().split()) M = int(sys.stdin.readline().strip()) # 갈 수 있는 경로 G = [[]for _ in range(N+1)] for m in range(M): p,..
백준 16236 아기 상어 (파이썬)
2022. 10. 9. 21:49
백준
풀이 및 해설(주석) from collections import deque import sys from heapq import heappush, heappop # sys.stdin = open('아기상어.txt', 'r') def find_shark(): for i in range(N): for j in range(N): if arr[i][j] == 9: return i, j def solve(): global size, eat, rst, visit, target Q = deque() # 일단 현재 상어 위치 찾아서 Q에 넣어주고, 상어가 있는 좌표를 방문 처리 sr, sc = find_shark() Q.append((sr, sc)) visit = [[0] * N for _ in range(N)] vis..
백준 17471 게리맨더링 (파이썬)
2022. 10. 8. 19:33
백준
아이디어 itertools를 사용해 구역의 조합을 구한다. 두 구역이 연결되어 있는지 확인해야 한다. 풀이 및 해설 import sys from collections import deque, defaultdict from itertools import combinations # sys.stdin = open('게리멘더링.txt', 'r') # 연결이 되어있는지 확인하는 함수 def is_connected(group): Q = deque() Q.append(group[0]) visit = [0] * (N+1) visit[group[0]] = 1 while Q: u = Q.popleft() for v in graph[u]: if v in group and visit[v] == 0: Q.append(v) vi..