[문제]https://www.acmicpc.net/problem/21608기본적인 구현문제로, 주어진 조건대로 착실하게 수행하면 되는 문제입니다.[초기화] def __init__(self): self.n = int(input()) self.student_info = [tuple(map(int, input().split())) for _ in range(self.n**2)] self.score = {0: 0, 1: 1, 2: 10, 3: 100, 4: 1000} self.grid = [[0] * self.n for _ in range(self.n)] self.friends_list = defaultdict(set) self.a..
Python
[문제]https://www.acmicpc.net/problem/1937 전체적인 탐색을 진행하는 문제로, 이동에 제약이 걸려있는 것이 특징입니다. 시작점이 정해져 있다면, 주어진 대로 탐색을 진행하면 되지만 이동하는 칸을 최대로 만들어야 하기 때문에 시작점을 특정할 수 없습니다. 러프하게 생각하면 주어진 격자를 전부 탐색하면서 DFS를 수행하면 되겠지만, 시간 초과가 발생하므로 이동한 내역을 따로 기록해서 불필요한 이동을 막아줘야 합니다. 이때 사용되는 개념이 DP로, 해당 문제는 DFS + DP가 혼합된 문제입니다.[초기화] def __init__(self): self.n = int(input()) self.graph = [list(map(int, input().spl..
[문제]https://www.acmicpc.net/problem/1599요즘 코테를 보면 문자열 문제가 많이 출제되고 있는 거 같습니다. 특정 유형이 정해진 문제가 아니라면 아이디어로 구현하는 느낌이라 개인적으로 어렵게 다가오는 유형 중 하나입니다. 문제의 요지는 새로운 문자 체계를 기준에 맞게 정렬하는 문제입니다. 문자 정렬은 문자 하나하나의 아스키 값을 바탕으로 정렬하기 때문에, 새로운 문자 체계에 맞는 키 값을 매핑하는 방식으로 문제를 해결했습니다.[초기화] def __init__(self): self.n = int(input()) self.words = [input() for _ in range(self.n)] self.answer = [](키, 값) 형..
[문제]https://www.acmicpc.net/problem/14499주사위를 굴릴 때마다 주사위가 어떻게 변화하는지 시뮬레이션하는 문제입니다. 주사위를 "굴린다." 라는 표현에서 값들이 회전한다는 느낌을 받았고, 자연스럽게 Deque 자료구조를 떠올릴 수 있었습니다.[초기화] def __init__(self): self.n, self.m, self.y, self.x, self.k = map(int, input().split()) self.grid = [list(map(int, input().split())) for _ in range(self.n)] self.commands = list(map(lambda x: int(x) - 1, input().split..
[문제]https://www.acmicpc.net/problem/2458처음에는 어떻게 풀어야 할지 고민했습니다. 그런데 그래프 이미지 하단에 설명을 보고 연결된 그리고 연결한 노드의 수가 n - 1일 때 등수를 알 수 있다는 것을 알게 됐고, 진입 노드의 수 + 진출 노드의 수를 계산하면 답을 구할 수 있겠다고 생각했습니다. 이를 위해 진입 그래프와 진출 그래프를 만들고 두 번의 DFS를 수행했습니다. 굉장히 부르트포스한 방법인데, Python 기준 3000ms대로 풀이가 통과됐고, 입력을 sys를 받았을 때 위와 같은 시간대로 통과됐습니다.[초기화] def __init__(self): self.n, self.m = map(int, input().split()) self...
[문제]https://www.acmicpc.net/problem/2109그리디하게 매 순간 가장 큰 강의료를 받을 수 있는지 확인하면 되는 문제입니다.[초기화] def __init__(self): self.n = int(input()) self.schedule = [list(map(int, input().split())) for _ in range(self.n)] self.visited = [False] * 10001 self.answer = 0강의는 특정 일자에 진행하는 것이 아닌, 제안받은 시점으로부터 d일 안에만 가서 강의를 진행하면 됩니다. visited는 이를 위해 어느 시점에 방문했는지 확인하기 위한 용도로 사용될 것입니다.[풀이] ..
[문제]https://www.acmicpc.net/problem/16954생각보다 손이 많이 갔던 문제입니다. 처음에 놓쳤던 부분은 벽이었습니다. 벽을 내릴 때, 순차적으로 내리지 않고 입력받은 순으로 처리하다 보니 잘못된 처리가 수행되었습니다. 다음으로 놓쳤던 부분은 이동한 벽과 캐릭터가 만났을 때 처리하는 것이었습니다, BFS를 사용하게 되면 하나의 방향이 아니라 이동 가능한 9개의 방향과 움직인 벽을 고려해야 하는데, 이를 어떻게 처리해야 할지 고민하는 데 많은 시간을 소요했습니다.[초기화] def __init__(self): self.grid = [list(input()) for _ in range(8)] self.walls = set((i, j) for i in r..
[문제]https://www.acmicpc.net/problem/18428백트래킹과 BFS가 조합된 문제입니다. 백트래킹을 통해 3개의 벽을 설치할 수 있는 경우의 수를 만들고, 모든 벽을 쌓았을 때 선생님이 학생들을 모두 찾아낼 수 있는지 확인하면 되겠습니다.[초기화] def __init__(self): self.n = int(input()) self.grid = [input().split() for _ in range(self.n)] self.directions = [[-1, 0], [1, 0], [0, -1], [0, 1]] self.teacher_pos = [[i, j] for j in range(self.n) for i in range(se..
[문제]https://www.acmicpc.net/problem/18427약간의 제약이 붙은 DP 문제입니다. 블록을 하나만 써야 한다는 조건을 신경을 써야 풀이가 가능하겠습니다.[초기화] def __init__(self): self.n, self.m, self.h = map(int, input().split()) self.blocks = [list(map(int, input().split())) for _ in range(self.n)][풀이] def solve(self): dp = [0] * (self.h + 1) # dp[x]: 높이가 x인 탑을 만드는 경우의 수 dp[0] = 1 # 높이 0을 만드는 경우의 수는 1 fo..
[문제]https://www.acmicpc.net/problem/1504조건이 있는 다익스트라 문제입니다. 해당 조건은 구현할 때 신경 써야 하는 부분은 아니므로 어려운 것은 없습니다. 단순히 주어진 정점을 반드시 찍어야 하므로, 각각에 대해서 최단 경로를 구하고 합해주면 해결할 수 있는 문제입니다.[초기화] def __init__(self): self.n, self.e = map(int, input().split()) self.graph = [[] for _ in range(self.n + 1)] for i in range(self.e): start, end, cost = map(int, input().split()) s..
