백준

[문제]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/18430주어진 위치에 모든 부메랑을 놔보며 강도를 최대로 만들어야 하는 문제입니다. 어떤 모양, 어떤 위치일 때 최대인지 모르기 때문에 백트래킹을 통해 모든 경우의 수를 검사하면 되겠습니다.[초기화] static int[][][] boomerangs = { // 부메랑의 4가지 형태를 표현 (중심 포함) {{0, 0}, {1, 0}, {0, 1}}, // 「 {{0, 0}, {0, 1}, {-1, 0}}, // ㄱ {{0, 0}, {-1, 0}, {0, -1}}, // 」 {{0, 0}, {0, -1}, {1, 0}} // ㄴ }; public static void ma..

[문제]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..

[문제]https://www.acmicpc.net/problem/17141바이러스 조합을 찾아서 BFS를 수행하는 문제입니다. 바이러스 조합을 찾는 이유는, 어느 위치의 바이러스를 선택했을 때 최소 시간으로 퍼뜨릴 수 있을지 모르기 때문입니다.[초기화] def __init__(self): self.n, self.m = map(int, input().split()) self.grid = [list(map(int, input().split())) for _ in range(self.n)] self.directions = [(-1, 0), (1, 0), (0, -1), (0, 1)] self.answer = float('inf')[풀이] def ch..

[문제]https://www.acmicpc.net/problem/13975 비용을 줄일 수 있는 가장 직관적인 방법은 비용이 가장 작은 파일 두 개를 선택해서 취합하는 것입니다. 취합된 파일을 다시 선택지에 두고, 다시 한번 비용이 가장 작은 파일 두 개 선택. 위 과정을 하나의 파일이 남을 때까지 반복하면 해결할 수 있는 그리디 문제로 Python이 아닌 경우 데이터의 자료형에 신경 써야 합니다.[초기화] public static void main(String[] args) throws IOException { t = Integer.parseInt(br.readLine()); for(int tc = 0; tc 합산되는 숫자들이 커질 것을 대비해, 처음부터 long 타입으로 데이터를 입력받습니다.[풀..

[문제]https://www.acmicpc.net/problem/7453시간제한이 무려 12초인 문제입니다. 대놓고 최적화를 요구하는 문제라는 것을 알 수 있습니다. 특정 값을 만들 수 있는 조합의 수를 찾는 것이 목표입니다. 이러한 문제 유형의 경우, 전부 계산하지 않고 부분으로 쪼개 해시에 저장해 값을 비교하는 것이 일반적입니다. 부르트포스하게 풀면 O(n^4)이지만 해시를 사용하면 O(n^2)에 풀 수 있습니다.[초기화] def __init__(self): self.n = int(input()) self.arr = [list(map(int, input().split())) for _ in range(self.n)] self.a, self.b, self.c,..

[문제]https://www.acmicpc.net/problem/16946이전 벽 부수고 이동하기 시리즈와는 상관없는 문제입니다. 처음에는 1인 위치마다 BFS를 사용하여 부르트포스하게 풀었습니다. 그 결과 시간 초과가 발생했고 최적화를 고민해야했습니다. 부르트포스하게 접근하는 방법을 생각했을 때를 생각하면, 공통되는 빈 공간을 지속적으로 탐색하는 상황이 발생하게 됩니다. 빈 공간은 유동적으로 바뀌는 것이 아니므로, 한 번 계산하면 해당 빈 공간과 인접한 다른 곳에서 탐색할 때 재탐색할 필요 없이 결과를 합산하면 됩니다.즉 위와 같이 첫 1에서 출발해 0인 빈 공간을 탐색한 뒤에는, 나머지 인접한 1에서 해당 빈 공간을 탐색할 필요가 없다는 것입니다. 어디서 출발하는 탐색할 빈 공간의 크기는 3이 자명하..

[문제]https://www.acmicpc.net/problem/4179동시에 발생하는 상황을 시뮬레이션해야 하는 문제입니다. 동시 시뮬레이션이라고 특별한 기법이 필요한 것은 아니고 진행 상황을 처리해두기만 하면 됩니다. 그렇기 때문에 코드 상에서, 불이 먼저 번지든, 지훈이가 먼저 이동하든 상관없습니다.[초기화] def __init__(self): self.r, self.c = map(int, input().split()) self.grid = [list(input()) for _ in range(self.r)][풀이] def search_jihoon(self): for i in range(self.r): for j in range(s..

[문제]https://www.acmicpc.net/problem/2212문제 난이도에 비해, 설명이 시원하게 와닿지 않은 문제였습니다.[초기화] def __init__(self): self.n = int(input()) self.k = int(input()) self.sensor = list(map(int, input().split()))[풀이] def solve(self): self.sensor.sort() distance = sorted(list(map(lambda i: self.sensor[i + 1] - self.sensor[i], range(self.n - 1)))) print(sum(distance[:self..

[문제]https://www.acmicpc.net/problem/2169 처음에는 다익스트라를  생각하고 문제에 접근했으나, 모든 정점을 확인할 수 없어 dp로 풀어낸 문제입니다. dp 문제답게 풀이가 길지 않습니다. 또한 코드트리에서 연습했던 dp 빈출 유형과 유사한 문제였습니다.[초기화] static BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); static StringTokenizer st; static int n, m; static int[][] map; public static void main(String[] args) throws IOException { st = new StringTokenizer(br..