[골드 4] 백준 20159 - 동작 그만. 밑장 빼기냐?
[골드 4] 백준 20159 - 동작 그만. 밑장 빼기냐?
2025.07.09https://www.acmicpc.net/problem/20159풀이플레이어가 번갈아 가면서 카드를 가져간다.짝수 번째(0, 2, 4 … )는 내차례, 홀수 번째는 상대 차례이다.마지막 카드 1장을 상다 차례에서 내가 가져도록 1번의 밑장 빼기를 허용한다.최대 점수를 얻기 위해 밑장 빼기를 어느 위치에서 할지를 결정해야한다.psum0 = [0] * N # 내 차례에서의 누적합psum1 = [0] * N # 상대 차례에서의 누적합psum0[0] = A[0]psum1[0] = 0for i in range(1, N): if i % 2 == 0: # 내 차례 psum0[i] = psum0[i - 1] + A[i] psum1[i] = psum1[i - 1] else: ..
[실버 4] 백준 29767 - 점수를 최대로 (파이썬)
[실버 4] 백준 29767 - 점수를 최대로 (파이썬)
2025.07.09https://www.acmicpc.net/problem/29767풀이길이가 N인 정수 수열 A가 주어지며, 누적합(A[0]부터 A[i]까지의 합)을 구해 전체 N개의 누적합 중 K개를 선택해서 합을 최대로 만들어야한다.N, K = map(int, input().split())A = list(map(int, input().split()))N은 원소 개수, K는 선택할 누적합 개수를 입력 받는다.psum = [0] * Npsum[0] = A[0]for i in range(1, N): psum[i] = psum[i - 1] + A[i]psum[i]는 A[0] + A[1] + … + A[i]를 의미하며, 즉, 누적합 배열을 만든다.psum.sort(reverse=True)print(sum(psum[:K]..
[플래티넘 5] 백준 1050 - 물약 (파이썬)
[플래티넘 5] 백준 1050 - 물약 (파이썬)
2025.07.08https://www.acmicpc.net/problem/1050풀이여러개의 기초 물약은 가격이 주어지고, 일부 물약은 다른 물약들로 조합하여 만들 있다.조합은 "LOVE=A+2B" 같은 형태로 주어진다.목표: 물약 “LOVE”를 만드는데 필요한 최소 비용 계산하는 것이다.N, M = map(int, input().split())stuff = {}N은 가격이 주어진 물약 수를 나타내며, M은 조합식 수를 나타낸다.for _ in range(N) : name, cost = input().split() cost = int(cost) stuff[name] = cost가격이 주어진 물약은 딕셔너리 stuff에 저장한다.formulas = [input() for _ in range(M)]LOVE ..
[골드 2] 백준 2461 - 대표 선수 (파이썬)
[골드 2] 백준 2461 - 대표 선수 (파이썬)
2025.07.07https://www.acmicpc.net/problem/2461분류 : 정렬 + 우선순위 큐링크 : https://www.acmicpc.net/problem/2461풀이N개의 반이 있고, 각 반에는 M명의 학생이 있음.각 학생마다 실력이 있고, 각 반에서 한 명씩 대표로 뽑아서 실력 차이를 최소로 하고 싶음.즉, N명의 대표를 뽑을 때 최소 실력차가 가장 작은 집합을 만들고, 그 차이를 출력해야 함.from queue import PriorityQueue• Python 표준 라이브러리의 우선순위 큐 (최소 힙 역할) 사용N, M = map(int, input().split())A = [list(map(int, input().split())) for _ in range(N)]N개의 반마다 M명의 학생 실..
[골드 5] 백준 23843 - 콘센트 (파이썬)
[골드 5] 백준 23843 - 콘센트 (파이썬)
2025.07.06https://www.acmicpc.net/problem/23843풀이총 N개의 기기를 충전해야 한다.충전기는 M개의 콘센트가 있다.각 기기를 충전하는 데 걸리는 시간이 배열 A로 주어진다.한 번에 M개까지 충전 가능하며, 각 콘센트는 병렬로 작동한다.모든 기기를 충전 완료하는 데 걸리는 최소 시간을 구하라.A.sort(reverse=True) # 시간이 긴 기기부터 우선 배정가장 긴 기기부터 먼저 처리해야 전체 시간이 줄어든다.그리디 전략: 긴 작업을 먼저 분산시켜야 부하가 치우치지 않음.pq = [0] * Mheapq.heapify(pq)pq: 각 콘센트의 누적 충전 시간을 관리처음엔 모두 0초 (아무것도 안 꽂힌 상태)heapq를 사용해서 가장 빨리 끝나는 콘센트를 찾기 용이하게 함 (최소 힙)f..
[실버 1] 백준 1629 - 곱셈 (파이썬)
[실버 1] 백준 1629 - 곱셈 (파이썬)
2025.07.05https://www.acmicpc.net/problem/1629풀이A^B % C를 직접 계산하면 시간 복잡도 O(B), 너무 크다.A^B = A^(B//2) * A^(B//2) (짝수일 경우)A^B = A^(B//2) * A^(B//2) * A (홀수일 경우)이를 이용해서 재귀적으로 절반씩 계산하면서 나머지를 구하는 방식을 사용한다. → 시간복잡도 O(log B)def power(a, b, c): if b == 0: return 1 # a^0 = 1 if b == 1: return a % c # a^1 % c = a % c x = power(a, b // 2, c) # A^(B//2) 값을 재귀 호출로 구함 if b % 2 == 0: ..
[골드 3] 백준 12784 - 인하니카 공화국 (파이썬)
[골드 3] 백준 12784 - 인하니카 공화국 (파이썬)
2025.07.04https://www.acmicpc.net/problem/12784풀이인하니카 공화국의 수도는 1번 정점(문제에서는 0번으로 인덱싱)이다.나머지 모든 정점은 루팡에 의해 공격받을 수 있고, 이들을 방어하기 위해 일부 간선에 폭탄을 설치해야 한다.폭탄은 정점에 도달하는 가장 짧은 경로에 설치되고, 그 간선의 최소 비용이 사용된다.최소한의 비용으로 모든 리프 노드를 보호하려고 할 때, 그 비용을 구하는 문제다.입력 및 그래프를 구성한다.N, M = map(int, input().split())adj = [[] for _ in range(N)]for _ in range(M) : a, b, c = map(int, input().split()) a -= 1 b -= 1 adj[a].appen..
[골드 2] 백준 2749 - 피보나치 수 3 (파이썬)
[골드 2] 백준 2749 - 피보나치 수 3 (파이썬)
2025.07.04https://www.acmicpc.net/problem/2749풀이이미지 출처 : https://velog.io/@cha-suyeon/python-피보나치-수열-만들기-점프투파이썬-종합문제-5번피보나치 수열은 위 그림 처럼 제일 초기 1에서 1을 더한 값이 2, 2와 1을 더한 값이 3, …, n - 1번째 값과 n을 더한값.. 이런식으로 계속해서 늘어나는 수열이다.결국 식을 작성하면 다음과 같다.Fn = Fn-1 + Fn-2 (n >= 2)이런식으로 n 이 17일때의 피보나치 수를 써보면 다음과 같다.0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597n이 주어졌을 때, n번째 피보나치 수를 구하는 문제이다.여기서 한가지 고려해..
[플래티넘 5] 백준 20188 - 등산 마니아 (파이썬)
[플래티넘 5] 백준 20188 - 등산 마니아 (파이썬)
2025.07.03https://www.acmicpc.net/problem/20188풀이트리 DP 또는 서브트리 크기 기반의 조합 계산을 사용한 문제이다.무방향 트리이며, 등상 마니아들은 경로 (a, b, c)를 선택할 때 항상 a → b → c 순으로 이동한다.단, b는 a와 c의 LCA(최소 공통 조상)이어야 한다.모든 (a, b, c) 쌍에서의 경우의 수를 계산해야한다.사용한 아이디어어떤 간선을 제거하면 트리가 두 개의 서브트리로 나뉘게 된다.해당 간선을 통해 만들어지는 (a, b, c)의 경우의 수는 다음 두개로 나뉜다.서브 트리 내부에서 a, c를 고르고 b가 그 루트인 경우 → sizes[i] * (sizes[i] - 1) / 2서브트리와 바깥에서 a, c를 하나씩 고르고 b가 그 경계인 경우 → sizes[i..
[실버 2] 백준 17213 - 과일 서리 (파이썬)
[실버 2] 백준 17213 - 과일 서리 (파이썬)
2025.07.03https://www.acmicpc.net/problem/17213풀이서로 다른 N개의 과일 중에서 M개를 훔쳐올 때, 적어도 1개씩은 훔치는 경우의 수를 구하는 문제이다.적어도 1개씩 N종료의 과일을 가져온다는 조건은 곧 M개의 과일을 N개의 상자에 각각 적어도 1개씩 넣는 방법의 수를 묻는 것과 같다.이는 중복 조합의 문제로 환원되며, 중복 조합의 식은 다음과 같다.answer = 1for i in range(1, M - N + 1) : answer *= (M - i) answer //= i위 코드는 nCr의 계산 중에서 n = M - 1, r = M - N을 계산하는 것이다.파이썬 내장 함수 없이 직접 계산이 가능하다. (Collection 모듈)코드# 백준 17213 - 과일 서리# 분..
[골드 2] 백준 1655 - 가운데를 말해요 (파이썬)
[골드 2] 백준 1655 - 가운데를 말해요 (파이썬)
2025.07.02https://www.acmicpc.net/problem/1655풀이max_pq는 왼쪽 절반, 즉 중간값 이하를 담고 최대 힙으로 운용한다. (파이썬에서는 -값을 넣어 사용)min_pq는 오른쪽 절반, 즉 중간값 초과를 담고 최소 힙으로 운용한다.입력값과 max_pq, min_pq에서 하나씩 빼서 총 3개의 숫자 후보를 만들고 정렬 후 재분배한다.중간값은 항상 max_pq의 top인 -max_pq[0]이 된다.max_pq = [1e9]min_pq = [1e9]1e9를 미리 넣어둔다. 즉 힙이 비어있을때 heappop 하기 위한 임시값이다.하지만 이건 비정상적인 초기값이고, 결과적으로 정답이 이상해 질 수 도 있다.a = [A[i]]a.append(-heapq.heappop(max_pq))a.append(..
[골드 4] 백준 1327 - 소트 게임 (파이썬)
[골드 4] 백준 1327 - 소트 게임 (파이썬)
2025.07.02https://www.acmicpc.net/problem/1327풀이배열 A를 K개의 연속된 수만큼 뒤집는 연산을 통해 오름차순 [1, 2, ..., N]을 만드는 최소 횟수를 구하는 문제다.상태공간이 최대 N!이므로, 모든 경우를 다 탐색하면 안 되고, BFS로 최소 횟수를 탐색해야 한다.리스트 상태를 hash 값으로 바꿔서 방문 여부를 체크한다.def list_to_hash(a): hash = 0 for i in range(len(a)): hash += a[i] hash *= (len(a) + 1) return hash리스트를 정수형 hash 값으로 변환.(다만 완전한 유일성 보장은 안 됨 → tuple(a)을 쓰는 것이 더 안전)단순한 방식이지만, 충돌 가능..
[플래티넘 5] 백준 1102 - 발전소 (파이썬)
[플래티넘 5] 백준 1102 - 발전소 (파이썬)
2025.07.01https://www.acmicpc.net/problem/1102풀이발전소가 N개 있고, 어떤 발전소는 작동 중(y), 어떤건 꺼져 있다. (N)작동 중인 발전소가 다른 발전소를 켜는 데 드는 비용이 주어진다. (A[i][j])발전소를 P개 이상 켜기 위해 최소 비용을 구하는 문제이다.켜는 순서와 조합에 따라 총 비용이 달라진다.즉 최적의 순서를 구해야한다.주요 알고리즘은 비트마스킹 + 메모이제이션을 사용한다.입력 처리는 다음과 같이 비교적 간단하게 입력 받는다.N = int(input())A = [list(map(int, input().split())) for _ in range(N)]S = input()P = int(input())캐시 초기화를 위해서 65536개의 캐시를 생성한다.cache = [-..
[골드 5] 백준 1354 - 무한 수열 2 (파이썬)
[골드 5] 백준 1354 - 무한 수열 2 (파이썬)
2025.07.01https://www.acmicpc.net/problem/1354풀이A(0) = 1 A(n) = A(n // P - X) + A(n // Q - Y) (n > 0)주어진 N에 대해서 A(N)을 구하는 문제이다.기본 수열 정의A(n)은 자기보다 작은 인덱스들의 결과를 이용해 계산됨 → 전형적인 DP 구조문제점N이 최대 10^12이기 때문에 일반적인 리스트 기반 DP(dp = [0]*(N+1))는 메모리 초과 → 딕셔너리 기반 메모이제이션 사용점화식 재귀 정의점화식에 따라 다음과 같이 재귀함수 작성A(n) = A(n // P - X) + A(n // Q - Y)기저 조건n 메모이제이션계산된 결과는 cache[n]에 저장해서 중복 호출 방지def dp(n): if n 재귀 함수를 정의한다.시간복잡도..
[골드 4] 백준 17404 - RGB거리 2 (파이썬)
[골드 4] 백준 17404 - RGB거리 2 (파이썬)
2025.06.30https://www.acmicpc.net/problem/17404풀이이 문제는 다이나믹 프로그래밍을 사용해서 최소 비용을 계싼하는 문제이다.각 집은 R(0), G(1), B(2) 중 하나의 색으로만 칠해야 하며, 이웃한 집은 같은 색이면 안된다.첫번째 집과 마지막 집도 같은 색이면 안된다.N개의 집이 있고, 각 집의 각 색상별 비용이 주어진다.즉, 첫번째 집과 마지막 집이 같은색이면 안된다는 조건 때문에 기존 RGB 거리 문제보다 살짝 까다롭다.그래서 사용한 전략은 다음과 같다.첫번째 집의 색상을 R, G, B 하나로 고정하고 시작한다. 즉 3가지 경우로 나눠서 각각 따로 계산한다.그 다음 집부터는 기존 RGB거리처럼 dp[i][j] = i번째 집을 j색으로 칠할 때의 최소 비용을 채워나간다.마지막 집..