Problem Solving117 [Problem Solving] BOJ 18111 : 마인크래프트 문제 링크 : https://www.acmicpc.net/problem/18111 N*M의 땅이 있을 때, 평탄화하는 데 걸리는 최소 시간과, 그 시간 동안 평탄화 된 땅의 최대 높이를 구하는 문제이다. 1. 평탄화 하기 이전에 땅에 있는 블럭 중에 가장 높이가 낮은 블럭의 높이를 minHeight에 저장한다.2. 평탄화 하기 이전에 땅에 있는 블럭 중에 가장 높이가 높은 블럭의 높이를 maxHeight에 저장한다.3. h를 [minHeight, maxHeight] 범위로 조정하면서, 땅을 h의 높이로 평탄화 할 수 있는지 확인한다. 이 과정에서 블럭을 쌓아 올리는 것은 블럭을 소모시키는 것이기 때문에, 블럭이 부족하면 블럭을 쌓지를 못한다. 그러므로 먼저 블럭을 제거해야 하는 영역에서 블럭을 제거해서 .. 2025. 2. 2. [Problem Solving] BOJ 16434 : 드래곤 앤 던전 문제 링크 : https://www.acmicpc.net/problem/16434 전형적인 구현 + 매개변수 탐색 문제이다. 문제에 나와있는대로 simulate함수를 구현한다. 그런데 영웅과 몬스터가 한 대 씩 딜을 주고 받는 것으로 구현한다면 시간이 초과된다. 그러므로 다음과 같이 계산해서 구한다. 영웅이 몬스터를 처치하기까지, 혹은 처치하기 전까지 필요한 타격의 수 = 몬스터의 현재 HP / 영웅의 공격력몬스터가 영웅을 처치하기까지, 혹은 처치하기 전까지 필요한 타격의 수 = 영웅의 현재 HP / 몬스터의 공격력 이 중 더 작은 값을 구해서 cnt에 저장한다. 그리고 다음을 계산한다.몬스터의 현재 HP -= 영웅의 공격력 * (cnt - 1)영웅의 현재 HP -= 몬스터의 공격력 * (cnt - 1).. 2025. 2. 1. [Problem Solving] BOJ 5052 : 전화번호 목록 문제 링크 : https://www.acmicpc.net/problem/5052 입력받은 문자열에서 한 문자열이 다른 문자열의 접두어라면 NO를 출력, 그런 경우가 없다면 YES를 출력하는 문제이다.위와 같은 자료구조를 Trie라고 한다.우선 입력받은 문자열을 모두 Trie 구조에 삽입한다.각각의 노드는 값과 자식 노드를 담는 리스트를 가지고 있다. Trie 구조에 문자열 number를 삽입하는 과정은 다음과 같다.1) 현재 노드의 자식 노드 중에서 number[0]와 같은 값을 가진 노드가 있다면, 그 노드에 number[1:]을 삽입한다.2) 현재 노드의 자식 노드 중에서 number[0]와 같은 값을 가진 노드가 없다면 값이 number[0]인 새로운 노드를 만들어서 현재 노드의 자식 노드 리스트에.. 2025. 1. 31. [Problem Solving] BOJ 3109 : 빵집 문제 링크 : https://www.acmicpc.net/problem/3109 R*C 그래프에서 graph[i][0]에서 graph[j][C - 1]까지 갈 수 있는 서로 겹치지 않는 경로의 최대 개수를 구하는 문제이다. graph[i][0]에서 시작되는 dfs를 수행하여 경로의 수를 구한다. 서로 겹치지 않는 경로의 최대 개수를 구해야 하기 때문에 이동 경로의 우선 순위를 {오른쪽 상단 -> 오른쪽 -> 오른쪽 하단}으로 설정한다. 위에 있는 시작점에서 최대한 위로 가려고 해야 밑에 있는 시작점으로 출발하는 dfs를 수행 시 갈 수 있는 선택지가 많아지기 때문이다. graph[j][C - 1]에 도달했다면 answer를 1 증가시키고 true를 return하면, graph[j][C - 1]부터 gra.. 2025. 1. 30. [Problem Solving] BOJ 4179 : 불! 문제 링크 : https://www.acmicpc.net/problem/4179 지훈이가 미로에서 탈출해야 하는 데, 불이 벽이 아닌 모든 곳으로 번지기 전에 탈출할 수 있는지, 그렇다면 몇분이 걸리는지 구하는 문제이다. 1. 불에 대한 BFS를 수행하여, 불이 있는 곳으로 부터 각 격자마다 번지게 되는 최소 시간을 계산한다. 불은 벽을 제외한 모든 곳에 번질 수 있다.2. 지훈이에 대한 BFS를 수행하여, 지훈이가 처음 존재하는 격자에서 다른 격자까지 가는데 걸리는 최소 시간을 각 격자마다 구한다. 지훈이는 불이 최초로 난 곳과 벽을 제외한 모든 곳으로 움직일 수 있다.3. 미로의 가장자리까지 불이 번지기 전에 지훈이가 도달할 수 있는 경우, 도달할 수 있는 시간 중 최소 시간을 구해서 출력한다. im.. 2025. 1. 29. [Problem Solving] BOJ 17404 : RGB거리 2 문제 링크 : https://www.acmicpc.net/problem/17404 문제를 이해하기 쉽게 생각하자면, 집들이 원형으로 있는 상태에서 각각의 집을 R, G, B로 칠해야하는 데, 인접하는 집이 같은 색깔이면 안된다는 가정 하에 칠하는 비용의 최솟값을 구하는 문제이다. 0번 집이 R색 일 경우의 answer의 최솟값, 0번 집이 G색일 경우의 answer의 최솟값, 0집이 B색일 경우의 answer의 최솟값을 구해서, 최솟값 중의 최솟값을 출력하면 된다. 우선 입력받은 테이블과 같은 사이즈의 DP 테이블을 만든다. DP 테이블의 원소는 모두 무한대로 설정한다.0번 집이 R색일 경우, dp[0][0]를 costs[0][0]로 설정하고, dp[i][j] = min(dp[i-1][j와 다른 색깔].. 2025. 1. 28. 이전 1 ··· 5 6 7 8 9 10 11 ··· 20 다음
