[골드 5] 백준 1419 - 등차수열의 합 (파이썬)
[골드 5] 백준 1419 - 등차수열의 합 (파이썬)
2025.05.07https://www.acmicpc.net/problem/1419풀이주어진 등차수열의 규칙은 다음과 같다.k = 2: 수열은 3, 4, 5, ... 이므로 x ≥ 3k = 3: 수열은 4, 7, 10, 13, ... → 일반항 3n + 1 → n ≥ 1k = 4: 수열은 4, 6, 8, 10, 14, 16, ... → 짝수 중에서 12만 빠짐k ≥ 5: 5n + 2 이고, n ≥ 2각 케이스마다 상한 (r)까지 몇 개 있는지와 하한 (l)보다 작은 부분까지 몇 개 있는지를 구해서 그 차이를 구한다.즉, f(r) - f(l - 1) 형태로 개수를 구한다.각각 K = 2 ~ 4, K ≥ 5일때의 상황을 구해야한다.k == 2 일때if k == 2 : upper = max(0, r - 2) lowe..
[실버 3] 백준 25418 - 정수 a를 k로 만들기 (파이썬)
[실버 3] 백준 25418 - 정수 a를 k로 만들기 (파이썬)
2025.05.06https://www.acmicpc.net/problem/25418풀이이 문제는 정수 A에서 출발해서 두가지 연산이 가능하다.1을 더하기 (x → x + 1)2배 만들기 (x → 2x)를 사용하여 목표 정수 K를 만드는 최소 연산 횟수를 묻는다.그래프 모델링각 정수 i를 노드로 보고,i → i+1, i → 2*i 두 개의 간선을 가진다.시작 노드는 A, 목표 노드는 K가 된다.최단 경로 탐색모든 간선의 가중치가 1이므로, 너비 우선 탐색(BFS)을 사용하면 시작점에서 목표점까지의 최소 간선 수(연산 횟수)를 구할 수 있다.구현 세부사항visit[i]: 정수 i에 한 번이라도 도달했는지 표시dist[i]: 시작 정수 A에서 i에 도달하기까지의 최소 연산 횟수queue: BFS용 덱(Deque)인접 리스트 ..
[실버 4] 백준 18242 - 네모네모 시력검사 (파이썬)
[실버 4] 백준 18242 - 네모네모 시력검사 (파이썬)
2025.05.05https://www.acmicpc.net/problem/18242풀이#으로 구성된 직사각형 모양에서 하나의 칸만 .으로 뚫려 있음.이 구멍이 어느 방향에 뚫려 있는지 출력해야 함: UP, DOWN, LEFT, RIGHTmin_y, max_y, min_x, max_x = 1e9, 0, 1e9, 0for i in range(N): for j in range(M): if B[i][j] == '#': min_y = min(min_y, i) max_y = max(max_y, i) min_x = min(min_x, j) max_x = max(max_x, j)“#”의 좌표 중 가장 위, 아래, 왼쪽, 오른쪽을 찾아 네모..
[골드 5] 백준 10710 - 실크로드 (파이썬)
[골드 5] 백준 10710 - 실크로드 (파이썬)
2025.05.05https://www.acmicpc.net/problem/10710풀이N개의 도시간 거리: D[1] ~ D[N]M일간 날씨 나쁨 정도: C[1] ~ C[M]도시 0 → 도시 N까지 정확히 N번 이동해야 함 (각 이동은 하루 소요)한 날에 이동하거나, 대기 가능이동일을 적절히 골라, 총 피로도 = D[i] * C[j]의 합이 최소가 되도록 해야 함이 문제는 배낭 문제의 변형 + 구간 DP 또는 최적 부분 구조를 활용한 다이나믹 프로그래밍 문제이다.먼저 dp[i][j]는 i일째까지 고려했을 때, j개의 도시를 이동한 최소 피로도를 나타낸다.dp = [[1e9] * (N + 1) for _ in range(M + 1)]dp[0][0] = 0예를들어서 dp[3][1] = 3 이라면 3일 동안 도시 한칸만 이동했..
[Level 3] 프로그래머스 - 가장 먼 노드
[Level 3] 프로그래머스 - 가장 먼 노드
2025.05.04https://school.programmers.co.kr/learn/courses/30/lessons/49189 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr풀이노드 1번부터 출발하여 최단 거리로 이동할 떄가장 멀리 있는 노드의 개수를 구하는 문제이다.간선 수 기준이며, 모든 간선은 양방향이다.모든 간선이 동일한 비용이기 때문에, BFS로 최단 거리를 구할 수 있다.각 노드까지의 최소 간선 수를 구한 뒤, 가장 큰 거리 값을 갖는 노드의 개수를 세면 된다.너무나도 자연스럽게 인접리스트는 무방향 그래프로 생성하고, 0-based index로 생성한다.adj = [[] for _ in range(n)]f..
[브론즈 1] 백준 10041 - 관광 (파이썬)
[브론즈 1] 백준 10041 - 관광 (파이썬)
2025.05.04https://www.acmicpc.net/problem/10041풀이W, H: 전체 지도 크기 (사용되지 않음)N: 방문할 지점 수P: 각 방문 지점의 좌표인접한 지점 (x1, y1) → (x2, y2)로 이동할 때 거리 계산 방식:y1 > y2일 때: 단순 맨해튼 거리|x1 - x2| + |y1 - y2|y1 ≤ y2일 때: 체스의 킹처럼 이동 (대각선 허용)max(|x1 - x2|, |y1 - y2|)answer = 0for i in range(N - 1): x1, y1 = P[i] x2, y2 = P[i + 1] # 방향을 통일 (x1 x2: x1, x2 = x2, x1 y1, y2 = y2, y1항상 x1 ≤ x2로 만들어 방향을 일관되게 처리한다.if..
[브론즈 2] 백준 10040 - 투표 (파이썬)
[브론즈 2] 백준 10040 - 투표 (파이썬)
2025.05.04https://www.acmicpc.net/problem/10040풀이N명의 선수에게 각각 가장 낮은 응모 번호 이상인 응모자 한 명씩을 배정한다.응모자는 B 리스트에, 선수의 응모 기준 번호는 A 리스트에 주어진다.가장 많은 응모자를 배정받은 선수의 번호(1-based)를 출력해야 한다.count = [0] * N # 각 선수에게 배정된 응모자 수for i in range(M): # 모든 응모자에 대해 for j in range(N): # 선수 순서대로 확인 if A[j] A[j] ≤ B[i]인 가장 첫번쨰 선수 J를 찾아서 B[i]를 배정한다.응모자는 한 번만 배정되며, 여러 선수가 가능하다면 가장 앞에 있는 선수에게 배정된다.max_vote = 0who = -1for i in..
[브론즈 2] 백준 14471 - 포인트 카드 (파이썬)
[브론즈 2] 백준 14471 - 포인트 카드 (파이썬)
2025.05.04https://www.acmicpc.net/problem/14471풀이N개의 포인트를 사용하여 M개의 카드를 구매하고 싶다.각 카드에는 (a, b)가 주어지며,a는 현재 모인 포인트 수b는 해당 카드의 포인트 카드 개수카드를 구매하기 위해서는 포인트가 a 이상이어야 한다.카드를 구매하면 b만큼 포인트가 오른다.목표는 총 N개의 포인트를 모으는 최소한의 비용을 계산하는 것.코드# 백준 14471 - 포인트 카드# 분류 : 그리디N, M = map(int, input().split())C = [list(map(int, input().split())) for _ in range(M)]C.sort(reverse=True)cost = 0for i in range(M - 1) : if C[i][0]
[골드 3] 백준 4179 - 불! (파이썬)
[골드 3] 백준 4179 - 불! (파이썬)
2025.05.03https://www.acmicpc.net/problem/4179풀이지훈이(J)는 미로에서 탈출해야 함.불(F)은 매 분마다 상하좌우로 번짐.지훈이는 1분에 1칸 이동 가능.벽(#)은 지나갈 수 없음.불이 도착한 시간보다 지훈이가 먼저 도착해야 탈출 가능.fire[][] 와 jihun[][] 배열fire[i][j]: (i,j)에 불이 도달하는 시간jihun[i][j]: (i,j)에 지훈이가 도달하는 시간1은 아직 도달하지 않은 상태while q1: ...먼저 모든 불의 위치에서 동시에 시작하여 BFS를 수행.(x, y) → (nx, ny)로 퍼져가며 fire[nx][ny] = fire[x][y] + 1로 시간 기록.while q2: ...지훈이가 이동할 수 있는 경로 탐색.이동하려는 칸이 불이..
[실버 5] 백준 31738 - 매우 어려운 문제 (파이썬)
[실버 5] 백준 31738 - 매우 어려운 문제 (파이썬)
2025.05.03https://www.acmicpc.net/problem/31738풀이이 문제는 시간에 매우 민감한 문제이다.# 백준 31738 - 매우 어려운 문제# 분류 : 수학import mathN, M = map(int, input().split())if N >= M : print(0)else : print(math.factorial(N) % M)대충 이렇게 math 패키지로 팩토리얼을 계산한 경우 시간 초과가 일어나게 된다. 아마 계속해서 수를 증가시키면서 곱하기 때문에 시간 초과가 일어나는것으로 보인다.먼저 N이 M보다 큰 경우에는 어떤 수로 나누어도 0이 나올 수 밖에 없다.수학적으로 N ≥ M인 경우 M은 N!의 약수가 되므로 N! mod M = 0이 된다예를들어서 5! = 120, M = 5인..
[골드 4] 백준 10830 - 행렬 제곱 (파이썬)
[골드 4] 백준 10830 - 행렬 제곱 (파이썬)
2025.05.03https://www.acmicpc.net/problem/10830풀이크기 N \times N의 정수 행렬 A가 주어짐자연수 B가 주어질 때,A^B \mod 1000 을 구하라(여기서 A^B는 행렬 곱 기준의 거듭제곱)내가 먼저 실수한 부분은 다음과 같다.A ** B → 원소별 제곱임 (X)for i in range(B): A = A @ A → 시간 초과 (X)풀이 순서를 생각하면 다음과 같다.팩토리얼 전처리0!부터 N!까지 전부 리스트에 저장 (O(N))분자 계산N!분모 계산K! * (N-K)!모듈러 역원 적용분모의 역원을 구해서 분자와 곱함최종 계산결과를 MOD로 나눈다✅ 정답 접근 (분할 정복)🔍 핵심 아이디어\( A^B = A^{B//2} \times A^{B//2} \) (짝수)\( A^B =..
[골드 1] 백준 11401 - 이항 계수 3 (파이썬)
[골드 1] 백준 11401 - 이항 계수 3 (파이썬)
2025.05.02https://www.acmicpc.net/problem/11401풀이이게 어떻게 정답률이 40%?이 문제는 조금 어렵다. 모듈로 연산(1000000007)이 포함된 큰 수의 이항계수를 다루기 때문에, 단순한 팩토리얼 연산으로는 시간 초과가 일어난다.입력으로는 정수 N, K가 들어오소, 수가 크므로 모듈로 연산이 필요하고, 나눗셈은 페르마의 소정리를 이용해야한다.먼저 이항 계수 공식은 다음과 같다.하지만 단순한 팩토리얼 계싼은 값이 너무 커져 오버플로우가 발생하거나 시간초과가 발생한다.따라서, 문제에서 요구한 1000000007로 모듈로 연산을 적용해야 한다.왜 일반적인 나눗셈이 안되는 건가요?→ 일반적으로 모듈러 연산에서는 나눗셈이 직접 불가능하다. → 대신 모둘러 역원을 이용해야한다.페르마의 소정리는..
[브론즈 4] 백준 14470 - 전자레인지 (파이썬)
[브론즈 4] 백준 14470 - 전자레인지 (파이썬)
2025.05.02https://www.acmicpc.net/problem/14470풀이음식의 초기 온도 A에서 목표 온도 B까지 가열해야 한다.조건에 따라 걸리는 시간이 다르다.냉동 상태(0°C 미만)은 1도 올리는 데 C초 걸림.0°C에서 해동하는 데 D초 소모.해동된 후(0도 이상) 1도 올리는 데 E초 걸림.if A 초기 상태가 냉동 상태이고, 목표도 냉동 상태인 경우에는 단순히 A부터 B까지 C초로만 가열한다.elif A 0: print(-A * C + D + B * E)A를 0까지 올리는데 -A * C초가 필요로 한다.그 다음, 0도에서 해동하는데 D초가 걸리고, 해동 후 B도 까지 올리는데 B * E초가 걸린다.총시간을 수식으로 나타내면 -A * C + D + B * E 초가 소요된다.else: ..
[실버 1] 백준 1713 - 후보 추천하기 (파이썬)
[실버 1] 백준 1713 - 후보 추천하기 (파이썬)
2025.05.01https://www.acmicpc.net/problem/1713풀이사진틀이 N개 있다.총 M명의 추천이 차례로 주어진다.이미 사진틀에 있는 학생은 추천 수만 증가한다.사진틀에 자리가 없으면,추천 수가 가장 적은 사람을 사진틀에서 제거만약 추천 수가 같으면 가장 오래된 사람을 제거마지막에 사진틀에 걸려 있는 학생 번호를 오름차순 출력count = [0] * 100 # 학생별 추천 수 (인덱스 = 학생 번호 - 1)last = [-1] * 100 # 학생별 마지막 추천받은 시간 (인덱스 = 학생 번호 - 1)학생 번호는 1 ~ 100까지 가능하다.count[i] 는 i번 학생의 추천수를 나타낸다.last[i]는 i번 학생이 사진틀에 걸린 시간을 나타낸다.for i in range(M): C[i] ..
[브론즈 2] 백준 1173 - 운동 (파이썬)
[브론즈 2] 백준 1173 - 운동 (파이썬)
2025.05.01https://www.acmicpc.net/problem/1173풀이현재 맥박 : m, 최대 맥박 : M운동 할 때마다 맥박 T만큼 증가쉬면 맥박 R만큼 감소운동을 N번 해야한다.현재 맥박이 M을 초과하면 운동을 못한다.운동을 못할 때는 쉬어야한다.운동 N번을 완료하는 데 걸리는 시간을 출력하고,만약 아예 운동을 못 시작하는 상황이면 -1을 출력한다.if m + T > M : print(-1)현재 맥박 m에 운동 후 증가량 T를 더했을 때, M을 넘으면,아예 한 번도 운동할 수 없기에 -1을 출력하고 종료한다.else : timer = 0 X = m while N > 0 : timer += 1타이머를 0으로 초기화 하고, 현재 맥박 X를 m으로 초기화한다.운동을 N번 해..