→

문제link: https://www.acmicpc.net/problem/12456 접근K값의 범위가 크기 때문에 입력받은 커피 정보(1 만족도 합계의 최대를 구해야 하므로 우선순위 큐 h에 커피 정보를 (-만족도, -개수) 형태로 삽입했고, 탐색하는 시점에서 소비 가능한(유통기한이 현 시점~k 범위인) 커피 정보만 h에 들어가도록 코드를 작성했다. 코드import sysimport heapqinput = sys.stdin.readlinet = int(input())for i in range(1, t+1): n, k = map(int, input().split()) coffee = [] h = [] for _ in range(n): ci, ti, si = map(int,..

문제link: https://www.acmicpc.net/problem/32946 접근고기가 있는 칸까지 이동하는 함수 ptom()과 최종 목적지 s까지 이동하는 함수 mtos()를 만들어 문제를 해결했다.고기가 반죽에 붙으려면 반죽에서 고기까지의 거리가 홀수 칸이어야 한다. 이를 고려해 반죽에 고기가 붙을 수 있는 경우에만 mtos()를 실행하도록 했다. 또, 고기와 반죽 사이에 또 다른 반죽이 있는 경우에는 장애물이 되는 반죽을 치울 수 있는지를 확인해야 한다. 코드import sysinput = sys.stdin.readlinedef ptom(p1, p2): cnt = float('inf') if p1

문제link: https://www.acmicpc.net/problem/1148 접근퍼즐판이 3*3 모양이라 문제를 읽기 전에는 워드스크램블 같은 다소 복잡한 문제일 줄 알았는데 전혀 아니었다. 각 단어에 대해 알파벳별로 사용된 알파벳 개수를 리스트에 저장하여 사용했다. 아스키코드를 활용해 인덱스에 접근하면 편하다. 코드import sysinput = sys.stdin.readlinewords = []while 1: word = input().rstrip() if word == '-': break tmp = [0]*26 for w in word: x = ord(w) - ord('A') tmp[x] += 1 words.append(tmp)wh..

문제link: https://www.acmicpc.net/problem/1930두 정사면체의 면에 어떤 색이 칠해져 있는지가 주어질 때, 두 정사면체가 같은 정사면체인지 확인하는 문제이다. 접근문제의 예제 입력은 정사면체의 각 면이 다른 색상으로 이루어지는 경우만 주어지지만, 문제 조건에 따르면 색상이 중복되어도 상관 없다. 이에 유의하여 코드를 작성해야 한다.두 번째 정사면체의 밑면 색이 첫 번째 정사면체의 밑면 색과 같도록 조정한 후 회전시키며 동일한지 확인하도록 코드를 작성했다. 코드import sysinput = sys.stdin.readlineside = ((1, 2, 3), (0, 3, 2), (3, 0, 1), (2, 1, 0)) for _ in range(int(input())): ..

문제link: https://www.acmicpc.net/problem/32015주어지는 문장이 하이쿠 형식에 맞는지를 판단하는 문제이다.하이쿠 형식에 맞는 문장이면 5·7·5 음절로 나누어 출력한다.그렇지 않으면 주어진 문장을 그대로 출력한다. 접근문제에서 음절 구분 기준을 제시하고 있으므로 그에 따라 코드를 작성하면 된다.조건이 많아서 코드가 다소 지저분해졌다 ㅎㅎ.주어지는 문장 내에서는 대소문자가 혼용될 수 있고 알파벳이 아닌 문자(마침표, 쉼표, 느낌표 등등) 또한 포함될 수 있다. 때문에 각 단어가 몇 음절인지 수월하게 체크하기 위해서 알파벳만 남긴 후 소문자로 일괄 전환하여 음절을 확인했다. 코드import sysinput = sys.stdin.readline#문장 입력받음s = list(i..

문제link: https://www.acmicpc.net/problem/268016진수로 인코딩된 데이터 블록을 받아 디코딩해 출력하는 문제이다. 접근16진수 데이터 블록을 2진수 형식으로 바꾼 후 앞에서부터 읽으며 문제에서 제시한 규칙에 따라 해독했다.터미네이션 코드 이후의 데이터 블록은 고려할 필요 없으므로 터미네이션 코드를 만나면 인코딩을 종료하면 된다. 코드import sysinput = sys.stdin.readline #i~i+cnt 구간 값을 십진수 형식으로 반환하는 함수def readBits(i, cnt): return i+cnt, int(b[i:i+cnt], 2)def numeric(i): i, cnt = readBits(i, 10) for _ in range(cnt..

문제link: https://www.acmicpc.net/problem/20668정점, 간선의 수와 간선 정보가 주어졌을 때, 출발지에서 목적지까지 이동하는 데 걸리는 시간의 최솟값을 구하는 문제이다. 접근문제 자체는 다익스트라로 접근하면 쉽게 풀 수 있다. 문제에서 (답안을) 소수점 9자리까지 정확히 출력할 것을 요구하고 있기 때문에 실수 나눗셈을 오차없이 구현해야 했다. 문제를 풀기 위해서는 필연적으로 거리를 속도로 나누어 이동 시간을 구해야 한다. 속도 값 k의 범위가 1 코드import sysimport heapqinput = sys.stdin.readlinen, m = map(int, input().split())graph = [[] for _ in range(n+1)]for _ in rang..

문제link: https://www.acmicpc.net/problem/31112 접근주어지는 두 식을 연립하면 풀 수 있는 문제이다. 코드import sysinput = sys.stdin.readlinewhile 1: try: m, q = map(int, input().split()) f = list(map(int, input().split())) g = list(map(int, input().split())) h = list(map(int, input().split())) for _ in range(q): a, b = map(int, input().split()) y = a ^ g[h[a]^b]..

문제link: https://www.acmicpc.net/problem/28240패스 경로가 교차하지 않도록 n명의 학생들을 각기 다른 좌표에 배치하는 문제이다.패스 연습은 다음과 같이 이루어진다.1. 인접한 번호의 학생끼리 패스(1-2, 2-3, ..., (n-1)-n, n-1)2. Kobe와 LeBron끼리 패스3. Curry와 Jordan끼리 패스 접근다양한 답이 나올 수 있는 재미있는 문제라고 생각한다.개발블로그에 쓸 만한 말은 아니지만 솔직히 나는 기하학에 젬병이다(ㅠㅠ) 하지만 이 문제는 기하학에 조예가 깊지 않은 사람도 머리를 굴려 보면 풀 수 있을 법한 문제 같아서 여러 그래프를 그리며 풀어 보았다.최종 답안은 첨부한 사진의 맨 아래 그래프와 비슷한 형태이다.(완전히 동일하진 않고 사용한 ..

문제link: https://www.acmicpc.net/problem/16517시작점 S에서 T까지 가는 가장 짧은 시간을 출력하는 문제이다. s에서 t로 이동할 때는 정확히 k1개의 빨간색 선로와 k2개의 파란색 선로를 사용해야 한다. 불가능하다면 -1을 출력한다. 접근우선순위 큐를 활용했고, dist[v][r][b]에 r개의 빨간색 선로와 b개의 파란색 선로를 사용해서 노드 v에 도달했을 때 걸리는 시간의 최솟값을 기록하도록 했다. 코드import sysinput = sys.stdin.readlineimport heapqn, m, k1, k2 = map(int, input().split())graph = [[] for _ in range(n+1)]for _ in range(m): u, v, ..