본문 바로가기

Problem Solving

 (11)
[백준 / BOJ] 2310 어드벤처 게임 (Rust) 문제 출처 : https://www.acmicpc.net/problem/2310 2310번: 어드벤처 게임 입력은 여러 개의 미로로 주어진다. 각 미로의 첫 줄에는 미로의 방 수를 나타내는 정수 n(1 ≤ n ≤ 1000)이 주어진다. 다음 n 줄에는 각 방의 정보가 주어진다. 각 방의 정보는 방의 내용물을 나타 www.acmicpc.net 1부터 n까지의 번호가 붙은 방이 있다. 각 방은 E,L,T로 이루어져 있는데, 각각이 의미는 아래와 같다. E : 비어있는 방 -> 아무런 동작도 하지 않음. L : 레프리컨의 방 -> 이 방에 진입했을때, 내가 갖고있는돈이 방의 돈 보다 작다면, 방의 돈으로 내 돈이 맞춰짐. T : 트롤의 방 -> 이 방에 진입하려면, 이 방의 돈 만큼 내가 돈을 갖고있어야 한다..
[백준 / BOJ] 14575 뒤풀이 (Rust) 문제 출처 : https://www.acmicpc.net/problem/14575 14575번: 뒤풀이 첫째 줄에 대회 참가자의 수 N과 술의 총량 T가 주어진다. (1 ≤ N ≤ 1000, 1 ≤ T ≤ 109) 둘째 줄부터 N개의 줄에 걸쳐, 각 사람에 대한 Li와 Ri값이 주어진다. (1 ≤ Li ≤ Ri ≤ 106) www.acmicpc.net 모든 사람은 각각 자신이 먹고싶어하는 최소주량 L 최대주량 R이 있다. 이 때, 도현이는 각각 의 사람들에게 최대 S만큼의 술을 나눠주며, 나눠준 술의 총 합을 정확히 T로 맞추는 S의 최솟값을 구하는 문제다. 풀이 문제에서 주어진 조건은 3가지 이다. 1. 모든 사람 i가 Li이상, Ri이하의 술을 받는다. 2. 모든 사람이 받은 술의 총합이 정확히 T ..
[백준 / BOJ] 12101 1, 2, 3 더하기 2 (cpp) 문제 출처 : https://www.acmicpc.net/problem/12101 12101번: 1, 2, 3 더하기 2 n을 1, 2, 3의 합으로 나타내는 방법 중에서 사전 순으로 k번째에 오는 것을 출력한다. k번째 오는 식이 없는 경우에는 -1을 출력한다. www.acmicpc.net 만들려는 숫자 n이 주어졌을때, n을 1,2,3을 이용해서 만들고 n을 만드는 경우의 수의 조합중 k번째를 찾아 출력하는 문제이다. 풀이 이런 유형의 DP를 풀어본적이 있어서 DP라고 착각했지만, n의 최댓값이 11로 작아서 완전탐색으로도 풀리는 문제다. 로직은 간단한데, 재귀를 이용해서 1,2,3으로 숫자 n을 만드는 모든 경우의 수를 저장해놓은다음 정렬 후 출력하면 된다. 주요 소스코드 void getComb(i..
[백준 / BOJ] 6209 제자리 멀리뛰기 문제 출처 : https://www.acmicpc.net/problem/6209 6209번: 제자리 멀리뛰기 첫 번째 줄에는 갇힌 돌섬으로부터 탈출구까지의 거리 d(1 ≤ d ≤ 1,000,000,000), 작은 돌섬의 수 n(0 ≤ n ≤ 50,000), 제거할 수 있는 작은 돌섬의 수 m (0 ≤ m ≤ n)이 공백으로 구분되어 주어진다. 두 www.acmicpc.net 시작지점(0번)에서 각각 일정 거리 떨어진 n개의 돌섬이 있다. 이때, n개의 돌섬중 m개를 제거하여 돌섬사이의 거리의 최솟값을 최대로 하는 문제이다. 풀이 문제에 나와있는 "최솟값을 최대"로 라는 키워드가 결정문제임을 알려주니 문제의 입력조건을 살펴보고 결정문제로 풀린다면 풀면 된다. 못 푼다면 DP로 풀면된다(모든 결정문제는 DP..
[백준 / BOJ] 23247 Ten (Java) 문제 출처 : https://www.acmicpc.net/problem/23247 23247번: Ten Your program is to read from standard input. The input starts with two positive integers $m$ and $n$ ($1 \le m, n \le 300$), denoting the dimensions of the land, which are given separated by a space. Each of the following $m$ lines contains $n$ positive in www.acmicpc.net N*M그리드에서 A*B범위의 사각형을 만들때, 그 사각형 범위안에 포함된 원소의 합을 10으로 만드는 사각형 범위의 갯수..
[백준 / BOJ] 2812 크게 만들기 (Java / 세그먼트 트리) 문제 출처 : https://www.acmicpc.net/problem/2812 2812번: 크게 만들기 N자리 숫자가 주어졌을 때, 여기서 숫자 K개를 지워서 얻을 수 있는 가장 큰 수를 구하는 프로그램을 작성하시오. www.acmicpc.net N자리의 수가 주어지며 이 수에서 K개의 숫자를 제거했을때 얻는 가장 큰 수를 구하는 문제이다. 풀이 세그먼트 트리로 푼 문제다. 문제를 N자리의 수에서 (N-K)개의 숫자를 선택하는 문제로 바꾼다면, 현재 선택가능한 범위 (left ~ right)에서 (N-K)번 숫자를 뽑아 최댓값을 만드는 문제로 바뀌게 된다. 이때, left ~ right의 범위는 최대 250,000만큼 차이가 날 수 있으므로, 완전탐색으로 현재 범위에서 최댓값을 찾는다면, (250,00..
[백준 / BOJ] 11780 플로이드 2 (Java) 문제 출처 : https://www.acmicpc.net/problem/11780 11780번: 플로이드 2 첫째 줄에 도시의 개수 n이 주어지고 둘째 줄에는 버스의 개수 m이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가 www.acmicpc.net n개의 도시와 n개의 도시를 연결하는 m개의 버스가 있을때, 각 도시를 오가기위해 지불해야하는 버스의 최소비용과 이때의 경로를 구하는 문제다. 풀이 푸는데 2일이나 걸린 문제다.. 경로를 찾는과정에서 생각보다 어려움을 겪었는데, Java언어가 String을 이어붙이는 메커니즘상(Java는 String을 붙일경우 새로운 String객체를 생성한다.) 각 경로를 비교해가며 최단경로를..
[백준 / BOJ] 5875 오타 문제 출처 : https://www.acmicpc.net/problem/5875 5875번: 오타 올바른 괄호쌍을 좋아하는 키파는 최근에 노트북을 샀다. 그런데 키보드의 크기가 너무 작았기 때문에, 키파는 혹시 여는 괄호와 닫는 괄호를 서로 잘못 입력하지 않았는지 걱정되었다. 키 www.acmicpc.net 오타가 '최대 한번' 있는 괄호배열이 주어진다. 이 괄호배열의 괄호를 하나 조작하여 올바른 괄호 배열을 만드는 경우의 수 를 구하는 문제다. 풀이 어려웠던 문제다 누적합으로 풀었는데, 여는 괄호를 +1, 닫는괄호를 -1 이라고 하고 누적합 배열을 만들자. 예를들어, 괄호배열 ( ) 의 누적합배열은 {1, 0}, ( ( ) ) 의 누적합 배열은 {1, 2 ,1, 0}이 된다. 올바른 괄호배열이 여는괄호..

티스토리툴바