Programming/백준
[골드 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색으로 칠할 때의 최소 비용을 채워나간다.마지막 집..
[실버 4] 백준 9575 - 행운의 수 (파이썬)
[실버 4] 백준 9575 - 행운의 수 (파이썬)
2025.06.30https://www.acmicpc.net/problem/9575풀이for a in A: for b in B: for c in C:세 배열 A, B, C에서 각각 하나씩 고른다 (총 경우의 수는 N × M × K).합 sum = a + b + c가 “행운의 수”인지 판별한다:10으로 나누며 각 자릿수가 5 또는 8만 있는지 확인함.조건을 만족하면 lucky 리스트에 추가.중복 제거 후 행운의 수 개수 출력.while sum > 0: if sum % 10 not in [5, 8]: good = False break sum //= 10sum의 각 자릿수를 검사함.5 또는 8이 아닌 숫자가 있으면 good = False로 탈락.코드# 백준 9575 - 행운..
[골드 4] 백준 14395 - 4연산 (파이썬)
[골드 4] 백준 14395 - 4연산 (파이썬)
2025.06.29https://www.acmicpc.net/problem/14395풀이from collections import dequeS, T = map(int, input().split())visit = set()path = {}queue = deque()queue.append(S)visit.add(S)path[S] = ""입력으로 정수 S, T를 받고 BFS용 자료구조 초기화한다.visit는 중복 연산 방지를 위한 방문 집합을 생성하고, path는 각 숫자에 도달한 연산 문자열을 저장한다.while len(queue) != 0 : u = queue.popleft()BFS 반복문을 시작한다. if u * u “*” 연산을 수행해서 새로운 값이 아직 방문하지 않았고, 10억 이하이면 큐에 넣는다.또한, 연..
[골드 2] 백준 1507 - 궁금한 민호 (파이썬)
[골드 2] 백준 1507 - 궁금한 민호 (파이썬)
2025.06.28https://www.acmicpc.net/problem/1507풀이모든 도시 쌍 사이 최단 거리가 주어졌을 때, 최소한의 도로만으로도 그 최단 거리 정보를 유지할 수 있는지를 묻고 있다.주어진 거리 행렬은 이미 모든 쌍 최단 거리 정보를 담고 있음 (플로이드 이후 결과)어떤 도로 i-j가 다른 경로 i-k-j에 포함되어 있다면, 굳이 필요하지 않음따라서 직접 연결된 간선 중, 다른 경로로 대체 가능한 간선은 제거주요 변수dist[i][j]: 도시 i에서 j까지의 최단 거리need[i][j]: i에서 j까지 직접 연결된 간선이 필요한가 여부impossible: 삼각 부등식이 깨지는 경우 (즉, 입력이 잘못된 경우)N = int(input())dist = [list(map(int, input().split..
[골드 2] 백준 3109 - 빵집 (파이썬)
[골드 2] 백준 3109 - 빵집 (파이썬)
2025.06.28https://www.acmicpc.net/problem/3109풀이가스관이 있는 빵집의 왼쪽 열에서 시작해 오른쪽 열까지 파이프를 설치할 수 있는 최대 개수를 구하는 것이다.'.'은 빈 칸, 'x'는 설치 불가능한 건물파이프는 오른쪽 위 / 오른쪽 / 오른쪽 아래로만 이동 가능파이프는 겹치면 안 됨출발은 각 행의 첫 번째 열 (즉, (i, 0))def dfs(r, c): visit[r][c] = True if c == C - 1: # 오른쪽 끝 도착 return TrueDFS는 3방향 우선순위로 탐색을 진행한다.오른쪽 위 (r - 1, c + 1)오른쪽 (r, c + 1)오른쪽 아래 (r + 1, c + 1)방문한 적 없고 빈 칸이면 DFS 재귀 호출, 도착 성공하면 True ..
[실버 2] 백준 2790 - F7 (파이썬)
[실버 2] 백준 2790 - F7 (파이썬)
2025.06.28https://www.acmicpc.net/problem/2790풀이N명의 학생이 있고 각 학생은 자신이 좋아하는 친구 수 B[i]를 갖고 있을 때, 가능한 한 많은 학생이 자신의 친구 수 조건을 만족하도록 친구를 맺도록 하는 것이다.i번 학생은 정확히 B[i]명의 친구를 갖고 싶어한다결국 이 문제는 B[i]명을 만족시키는 친구 매칭이 가능한 최대 학생 수를 구하는 것이다.이를 해결하기 위해, 학생들을 좋아하는 친구 수 기준으로 정렬하고, 뒤에서부터 만족시킬 수 있는지 확인한다.N = int(input())B = [int(input()) for _ in range(N)]B.sort()학생수와 각 학생이 원하는 친구 수 B[i]를 리스트에 저장한 뒤 오름차순 정렬한다.answer = 0max_val = 0..
[골드 3] 백준 25381 - ABBC (파이썬)
[골드 3] 백준 25381 - ABBC (파이썬)
2025.06.27https://www.acmicpc.net/problem/25381풀이문자열 S가 주어지며, S에서 문자 B는 한번씩만 사용할 수 있다.B앞에 A가 있으면 AB짝을 만든다.B뒤에 C가 있으면, BC 짝을 만든다.AB 또는 BC 쌍을 최대한 많이 만들어야하며, 단 하나의 B는 한번만 사용할 수 있다.B의 위치를 저장하기 위해서 다음과 같이 정의한다.queue = deque()for i in range(len(S)) : if S[i] == 'B' : queue.append(i)문자열에서 B의 인덱스 위치를 모두 deque에 저장하고, 앞뒤에서 모두 사용할 수 있게 deque를 사용한다.다음은 BC를 매칭한다. (왼쪽 → 오른쪽)for i in range(len(S)) : if S[i]..
[골드 1] 백준 1113 - 수영장 만들기 (파이썬)
[골드 1] 백준 1113 - 수영장 만들기 (파이썬)
2025.06.26https://www.acmicpc.net/problem/1113풀이높은 정보가 주어진 N * M 격자판이 존재한다.외곽은 절대 물을 담을 수 없고, 안쪽에 고인 물의 양을 계산해야한다.물은 본의의 높이보다 낮은 곳에 채워질 수 있다.각 칸에 고일 수 있는 물의 양을 계산해서 전체 합을 출력한다.결국 BFS로 해결해야 한다고 생각된다.모든 칸을 순회하면 (i, j) 칸에 물 1단계씩 채워보며 시도한다.채웠을 때 외곽까지 닿을 수 있다면 물은 새기 때문에 그만 둔다.외곽까지 닿지 않으면 물이 고일 수 있으므로 해당 칸 높이를 올리고 answer += 1을 진행한다.이 과정을 해당 칸에서 물이 넘칠 때 까지 반복한다.BFS 탐색으로 물이 새는지 확인하기 위해서 다음과 같이 정의 했다.while True : ..
[실버 2] 백준 13423 - Three Dots
[실버 2] 백준 13423 - Three Dots
2025.06.25https://www.acmicpc.net/problem/13423풀이다음 조건을 만족하는 수열 내 세 수 a, b, c의 개수를 찾는것이다.a b - a = c - b, 즉 등차수열 (공차 일정한 수열)정렬된 수열 A에서 두 수 A[i], A[j]를 선택하고, 공차를 구해서 등차수열의 세 번째 수 c = 2 * A[j] - A[i]가 A에 존재하는지를 판단한다.A는 정렬되어 있지만, 존재 여부를 빠르게 체크하기 위해 set으로도 관리한다.a 코드# 백준 13423 - Three Dots# 분류 : 자료구조T = int(input())for _ in range(T) : N = int(input()) A = list(map(int, input().split())) S = set(A) ..
[골드 2] 백준 2878 - 캔디캔디 (파이썬)
[골드 2] 백준 2878 - 캔디캔디 (파이썬)
2025.06.25https://www.acmicpc.net/problem/2878풀이총 M개의 캔디를 N명의 학생에게 나눠줘야 한다.각 학생은 자신이 원하는 캔디 수가 있고, 그보다 적게 받으면 “화남 지수”가 받은 개수^2로 증가한다.M개를 어떻게 배분해야 전체 화남 지수의 합이 최소가 되도록 하는지가 문제이다.사용한 풀이 전략은 다음과 같다.1. 이분 탐색을 이용해 평균 컷 구하기학생마다 min(A[i], mid) 만큼 주는 방식을 생각한다.이 때 mid를 조절하며, 총 줄 수 있는 캔디가 M 이상이 되는 최소 mid를 찾는다.mid 이상을 주면 안 되고, 모든 학생에게 최대한 공평하게 적게 주자는 전략.2. 이분 탐색 후 배분최적의 컷 수 p를 찾았으면,모든 학생에게 min(p - 1, A[i])만큼 먼저 배분한다..
[실버 5] 백준 12871 - 무한 문자열 (파이썬)
[실버 5] 백준 12871 - 무한 문자열 (파이썬)
2025.06.25https://www.acmicpc.net/problem/12871풀이두 문자열 S와 T가 무한히 반복된다고 할 때, 그 두 무한 문자열이 같은지 확인하는 문제이다.S = ‘abab’이고 T = ‘ababab’면 무한히 반복하면 둘 다 “abababababab…” 같은 문자열이 된다면 1을 출력하고 아니면 0을 출력한다.결국 핵심 아이디어는 문자열의 기본 단위를 구해서 비교하는 것이다.def find_basis(s): ...find_basis함수는 문자열 s의 반복되는 최소 단위를 찾아준다.예를 들어서 abab가 들어가면 ab를 반환하고, aaaa 가 들어가면 a를 반환한다.작동 방식은 다음과 같다.문자열 길이의 약수들을 기준으로 자른다.해당 길이로 자른 모든 조각이 동일한지 확인한다.동일하면 그것..
[실버 1] 백준 1141 - 접두사 (파이썬)
[실버 1] 백준 1141 - 접두사 (파이썬)
2025.06.24https://www.acmicpc.net/problem/1141풀이이 문제는 주어진 문자열들 중 다른 문자열의 접두사가 아닌 문자열의 개수를 세는 것이다.N = int(input())S = [input() for _ in range(N)]S = list(set(S)) # 중복 제거먼저 문자열 개수 N을 입력받고, 문자열 리스트 S를 구성한 뒤 set()을 이용해 중복 문자열을 제거한다.prefix = [False] * Nprefix[i]는 S[i]가 다른 문자열의 접두사인지 여부를 저장하는 배열이다.for i in range(len(S)) : for j in range(len(S)) : if i == j : continue if len(S[i]) >..
[골드 4] 백준 16120 - PPAP (파이썬)
[골드 4] 백준 16120 - PPAP (파이썬)
2025.06.23https://www.acmicpc.net/problem/16120풀이문자열이 PPAP 규칙에 따라서 만들어졌는지 판별하는 문제이다.기본적인 규칙은 PPAP는 P로 줄일 수 있다.PPPAP는 PPAP + P → PP가 되지 않으므로 올바른 형태가 아니다.줄이고 줄이다가 마지막에 P 하나만 남으면 PPAP 문자열이라고 한다.S = input()stack = []입력 문자열 S를 한글자씩 처리할 것이며, 처리 중간 결과를 저장하기 위해서 스택을 사용한다.for i in range(len(S)) : stack.append(S[i])입력 문자열의 각 문자를 stack에 순차적으로 쌓는다.while len(stack) >= 4 and "".join(stack[-4:]) == "PPAP" : for _ ..
[골드 3] 백준 1670 - 정상 회담 2 (파이썬)
[골드 3] 백준 1670 - 정상 회담 2 (파이썬)
2025.06.22https://www.acmicpc.net/problem/1670풀이사람 수는 짝수 N이고, 각 사람은 한 명과만 악수할 수 있으며, 악수 선이 교차하지 않아야 한다.이는 DP로 해결할 수 있으며, 다음 점화식을 따른다.이 문제는 카탈란 수(Catalan Number) 문제 유형의 대표적인 예다.핵심은 다음과 같다N명의 정상 중 한 명을 기준으로 짝을 지었을 때, 남은 좌우 인원들도 각각 교차 없이 짝을 지어야 한다.이를 이용하면 DP 점화식을 다음과 같이 세울 수 있다.D[0] = 1 # 아무도 없을 때는 1가지 (아무것도 안 하는 경우)D[2] = 1 # 두 명이 있을 때는 1가지D[n] = D[0]*D[n-2] + D[2]*D[n-4] + D[4]*D[n-6] + ... + D[n-2]*D[0]..
[실버 1] 백준 12849 - 본대 산책 (파이썬)
[실버 1] 백준 12849 - 본대 산책 (파이썬)
2025.06.21https://www.acmicpc.net/problem/12849풀이총 8개의 장소(0~7번 정점)로 구성된 캠퍼스가 있고, 하루에 1분씩 이동할 수 있음.이동 가능한 경로는 문제에서 고정되어 있음 (총 12개 간선)0번에서 시작해 정확히 D분 뒤 다시 0번에 도착할 수 있는 모든 경로의 수를 구하는 문제.단, 결과는 10^9 + 7로 나눈 나머지를 출력.adj = [[] for _ in range(8)]edge = [ ... ] # 문제에서 주어진 12개 간선for a, b in edge: adj[a].append(b) adj[b].append(a)먼저 인접 리스트를 정의하고, adj[i]는 i번 정점에서 갈 수 있는 이웃 정점을 리스트로 담고 있다.양방향 그래프이므로 adj[a].app..