전체 글115 [BOJ] 외판원 순회 (2098, G1) 정말로 개고생한 문제입니다..... 풀이도 보고, 설명도 듣고 이것저것 찾고... 3시간 걸렸습니다...정답 코드import sysinput = sys.stdin.readlineINF = 10**15def dfs(cur_v, visited): # 모두 방문: 시작(0)으로 귀환 # 현재 방식에서는 이게 마지막 단계이므로 마지막을 합쳐준다. if visited == ALL: return graph[cur_v][0] if graph[cur_v][0] > 0 else INF # 메모이제이션 if dp[visited][cur_v] != -1: return dp[visited][cur_v] best = INF for next_v in range(N):.. 2025. 11. 11. [BOJ] 어려운 소인수분해 (16563, G4?) 소인수 분해 문제가 무려 G4인 세계선이 존재한다고?https://www.acmicpc.net/problem/16563 풀이법 1. 에라토스테네스의 체 활용가장 쉽게 할 수 있는 풀이법입니다.import sysinput = sys.stdin.readline# 어려운 소인수 분해 풀이 1 - 에라토스테네스의 체# 선형 체라는 방법도 있다는데, 일단 이거부터.# 수가 많아야 500만까지다. 500만의 0.5제곱 까지의 수만 봐도 된다.# Python으로는 시초가 난다. 더 좋은 방법이 없을까?MAX = 5000000cutline = int(MAX ** 0.5) + 1prime_check = [True for _ in range(cutline+ 1)]for i in range(2, int(cutline ** .. 2025. 11. 9. [BOJ] 퍼즐 (1525, G2) 아이디어는 BFS를 활용한 빡구현. 처음에 퍼즐판에 나올 수 있는 경우를 확장하여 9!로 visited를 생성하고,최단 턴 수 이므로, 한 번 나온 배열은 다시 나오지 않게 처리한다.이 때, 퍼즐의 이동을 2차원 배열이 아닌 문자열로 처리.더불어, 명백하게 풀이가 불가능한 케이스로 예외 처리를 하여 조금 속도 이득을 보려고 했는데... 비효율 풀이 같다...import sysfrom collections import dequeinput = sys.stdin.readlinedef dfs(level, ans): if level == 9: puzzle_dict[ans] = False return else: for i in range(0, 9): .. 2024. 12. 15. [BOJ] 814-1 (16972, B1?) 문제 설명주어진 조건에 맞는 814개의 점을 찾아야 합니다. 주의사항은, 가장 가까운 두 점의 쌍이 여러개여서는 안 된다. 입니다..즉, 단순히 직사각형으로 점들을 배치했다가는 가장 가까운 두 점의 쌍이 여러개이므로 오답! 입니다. 생각의 단계1단계. 일단 풀기먼저 가장 쉽게 생각할 것은, 임의로 점을 뿌리면 두 점의 거리가 같은 쌍이 두 개 이상 나올 가능성이 매우 적습니다. 이렇게 하면 일단 정답은 맞힐 수 있습니다.import randomfor i in range(814): a=random.randint(-8140,8140) b=random.randint(-8140,8140) print("%d %d"%(a, b)) 하지만 이대로는 고득점을 맞기는 어렵겠죠? 점수를 더 높혀봅시다. .. 2024. 12. 2. [BOJ] 성냥개비 (3687, G2) 문제풀이 아이디어각 숫자마다 쓰이는 성냥개비가 달라서, 명백하게 어떤 일반항을 찾기는 어렵지만 어느 정도 통제가 가능합니다.같은 개수가 사용된 성냥개비 중 최댓값을 만들기 위해서는 가장 큰 숫자, 최솟값을 만들기 위해서는 가장 작은 숫자가 필요합니다.단! 최솟값의 경우 맨 앞에 0이 와서는 안됩니다. 따라서 6으로 대체하고, 맨 앞이 아닌 6은 모두 0으로 대치하는 별도의 추가 과정이 필요합니다.근데 이걸 그냥은 알기가 어렵습니다. 최초 2~7획에서도 최대/최소의 케이스가 달라지므로 다음과 같이 생각합니다.먼저 2, 3개는 그냥 초항으로 계산합니다.4개째부터는 2~7획이전의 결과를 살펴보아, 그냥 자체로 최대/최소인지, 이전의 결과에 특정 숫자를 앞뒤로 붙여 최대/최소인지 모두 확인합니다. 그리고 가장 .. 2024. 12. 2. BOJ 티어 플래 달성! 드디어 플래티넘 5를 찍었습니다. 아직은 많이 물플래 입니다...기여할 수 있는 티어에 올라왔다는 것 만으로도 만족(?) 입니다. 아직 기본기가 많이 부족하여 부끄러운 플래입니다.부끄럽지 않은 플래티넘이 되도록 열심히 수련하겠습니다. 2024. 12. 1. 이전 1 2 3 4 ··· 20 다음
