Algorithm

[백준] 15846. 퇴사 2 - Python

[Gold V] https://www.acmicpc.net/problem/15486 15486번: 퇴사 2 첫째 줄에 N (1 ≤ N ≤ 1,500,000)이 주어진다. 둘째 줄부터 N개의 줄에 Ti와 Pi가 공백으로 구분되어서 주어지며, 1일부터 N일까지 순서대로 주어진다. (1 ≤ Ti ≤ 50, 1 ≤ Pi ≤ 1,000) www.acmicpc.net 풀이 1 문제를 보니, Greedy는 아닌 것 같고.. DP로 접근해야겠다는 생각으로 문제를 읽기 시작. 첫 시도에는, 1차원 dp이고, 1일차 부터 Bottom-Up으로 채워나가는 식으로 접근하려고 시도했다. 예제 입력 1 은 아래와 같다. 1일2일3일4일5일6일7일 Ti3511242Pi102010201540200 이런 상황에서, 1일차부터 접근하면..

[백준] 1277. 발전소 설치 - Python

[Gold IV] https://www.acmicpc.net/problem/1277 1277번: 발전소 설치 첫 줄에는 발전소의 수 N(1 ≤ N ≤ 1,000)과 현재 남아있는 전선의 수 W(1≤ W ≤ 10,000)가 주어진다. 두 번째 줄에는 제한 길이 M(0.0 < M < 200,000.0)가 주어진다. 다음 N개의 줄에는 1번 발전소부터 N번 발 www.acmicpc.net 풀이 우선, N M: graph[i][j] = 1e9 # 이미 연결된 전선의 cost(거리)는 0으로 for _ in range(W): a, b = map(int, input().split()) graph[a-1][b-1] = 0 graph[b-1][a-1] = 0 # 다익스트라 distance = [1e9]*N distan..

[백준] 2504. 괄호의 값 - Python

[Gold V] https://www.acmicpc.net/problem/2504 2504번: 괄호의 값 4개의 기호 ‘(’, ‘)’, ‘[’, ‘]’를 이용해서 만들어지는 괄호열 중에서 올바른 괄호열이란 다음과 같이 정의된다. 한 쌍의 괄호로만 이루어진 ‘()’와 ‘[]’는 올바른 괄호열이다. 만일 X www.acmicpc.net 풀이 기본적으로, 문제를 보자마자 Stack을 활용해 풀어야겠다고는 생각이 들었다. 처음에는 단순하게 닫을 때마다 x2, x3을 해 주면 될 것이라고 생각했는데, 보다 보니 금방 (()[]) 같은 경우, 안에서 더해준 다음 밖에서 한 번에 곱해줘야 한다는 것을 알았다. ((2+3)x2) 따라서, Stack에 숫자를 같이 넣는 형식으로 생각하여 풀이하였다. 여는 괄호일 때는 항..

[백준] 12904. A와 B - Python

[Gold V] https://www.acmicpc.net/problem/12904 12904번: A와 B 수빈이는 A와 B로만 이루어진 영어 단어가 존재한다는 사실에 놀랐다. 대표적인 예로 AB (Abdominal의 약자), BAA (양의 울음 소리), AA (용암의 종류), ABBA (스웨덴 팝 그룹)이 있다. 이런 사실에 놀란 수 www.acmicpc.net 풀이 우선 두 가지 연산을 했을 때 어떤 일이 발생하는 지 생각하자. 문자열의 뒤에 A를 추가한다. 이 연산은 단순하게 맨 뒤에 A를 추가할 뿐이다. 문자열을 뒤집고 뒤에 B를 추가한다. 이 연산은 맨 앞에 B를 추가하고 뒤집는 것과 동일한 연산이다. -> (이 때, 문자열을 뒤집는 것을 다르게 생각하면, 문자열은 그대로 두고 뒤에서부터 센다고..

[백준] 14254. 비밀번호 변경 - Python

[Gold V] https://www.acmicpc.net/problem/14254 14254번: 비밀번호 변경 첫째 줄에 예전 비밀번호가 주어진다. 비밀번호의 길이는 50을 넘지 않으며, 알파벳 소문자로만 이루어져 있다. 둘째 줄에 K가 주어진다. K는 예전 비밀번호의 길이를 넘지 않는 자연수이다. www.acmicpc.net 풀이 우선 전체 길이의 1/2 보다 K가 작다면, 그냥 똑같이 맞춰주면 되므로 크게 어렵지 않다. 전체 길이의 1/2 보다 K가 클 때가 문제인데, 겹치는 부분의 어느 한 값을 바꾸면, 앞의 k개와 뒤의 k개로 나누었을 때 두 쪽 모두 영향을 받기 때문이다. 따라서, 겹치는 부분은 항상 팰린드롬(Palindrome) 이 된다. 겹치는 부분 말고, 다른 부분들로부터 생각해 보자. ..

[백준] 21608. 상어 초등학교 - Python

[Gold V] https://www.acmicpc.net/problem/21608 21608번: 상어 초등학교 상어 초등학교에는 교실이 하나 있고, 교실은 N×N 크기의 격자로 나타낼 수 있다. 학교에 다니는 학생의 수는 N2명이다. 오늘은 모든 학생의 자리를 정하는 날이다. 학생은 1번부터 N2번까지 번호 www.acmicpc.net 풀이 3

[백준] 16236. 아기 상어 - Python

[Gold III] https://www.acmicpc.net/problem/16236 16236번: 아기 상어 N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 물고기가 최대 1마리 존재한다. 아기 상어와 물고기는 모두 크기를 가 www.acmicpc.net 풀이 우선 그래프 내에서 가장 가까운 칸을 찾기 때문에, BFS로 풀어야 하는 것은 바로 생각이 났고, N 가장 왼쪽 순으로 나열. return list(sorted(prey, key=lambda x: (x[0], x[1], x[2]))) second = 0 size = 2 eat = 0 while True: r, c = shark M[r][c] = size prey =..

[백준] 3109. 빵집 - C++

[Gold II] https://www.acmicpc.net/problem/3109 3109번: 빵집 유명한 제빵사 김원웅은 빵집을 운영하고 있다. 원웅이의 빵집은 글로벌 재정 위기를 피해가지 못했고, 결국 심각한 재정 위기에 빠졌다. 원웅이는 지출을 줄이고자 여기저기 지출을 살펴보던 www.acmicpc.net 풀이 우선, 찬찬히 살펴보면, 첫 번째 열의 모든 칸에서부터, 최대한 많이 마지막 열의 칸으로 연결해야 한다. 이 때, Greedy하게 첫째 열의 맨 위(첫 번째) 칸에서부터 시작해도 되며, 오른쪽 위 / 오른쪽 / 오른쪽 아래 3개의 선택지 중, 오른쪽 위를 선택하는 것이 이후 파이프 연결에서 가장 유리하므로, 또한 Greedy하게 오른쪽 위 - 오른쪽 - 오른쪽 아래 순으로, 가능한 선택지를..