본문 바로가기

알고리즘

(151)
[백준 / 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] 1091 카드 섞기 문제 출처 : https://www.acmicpc.net/problem/1091 1091번: 카드 섞기 지민이는 카지노의 딜러이고, 지금 3명의 플레이어(0, 1, 2)가 있다. 이 게임은 N개의 카드를 이용한다. (0 ~ N-1번) 일단 지민이는 카드를 몇 번 섞은 다음에, 그것을 플레이어들에게 나누어 준다. 0 www.acmicpc.net N장의 카드를 3명의 플레이어에게 나눠줄려고 한다. 카드를 주어진 조건 S를 이용해 섞어서 P에 맞게 나눠줄 수 있는지 구하는 문제이다. 풀이 지문이 난해한 문제다. 지문만 이해한다면, 시뮬레이션으로 풀면 되는데, 이때 최댓값을 계산 해줘야 한다. 이렇게 하면 안되지만... 나는 최댓값 계산에 실패해서 백준 채점 시스템을 이용해서 가지를 쳐가며 풀었다. 따라서, 증..
[백준 / BOJ] 20010 악덕 영주 혜유 (Java) 문제 출처 : https://www.acmicpc.net/problem/20010 20010번: 악덕 영주 혜유 FT온라인 게임에서 치열한 경쟁을 통해 영주가 된 혜유는 퀘스트를 받았다. 퀘스트의 내용은 자신이 관리하고 있는 마을 사이에 교역로를 건설하여 마을 간 교류를 활성화시키는 것이다. 이때, www.acmicpc.net N개의 마을과 마을을 연결하는 K개의 간선이 주어진다. 이때, K개의 간선을 이용해서 모든 마을을 연결하는 최소비용과 이때 마을사이를 연결하는 거리의 최댓값을 구하는 문제이다. 풀이 최소스패닝트리 알고리즘과 트리의 지름을 구하는 알고리즘을 각각 사용해서 푸는 문제다. 두 알고리즘을 섞어서 사용할 필요는 없고, "모든 마을을 연결하는 최소비용"을 MST를 이용해서 구한후, MST를 ..
[백준 / BOJ] 1124 언더프라임 문제 출처 : https://www.acmicpc.net/problem/1124 1124번: 언더프라임 자연수 X를 소인수분해하면, 곱해서 X가 되는 소수의 목록을 얻을 수 있다. 예를 들어, 12 = 2 × 2 × 3이다. 1은 소수가 아니다. 어떤 수 X를 소인수분해 해서 구한 소수의 목록의 길이가 소수이면, www.acmicpc.net 두 양의 정수 A,B가 주어졌을때, A,B사이의 언더프라임을 구하는 문제다. 여기서 언더프라임은 정수의 소인수분해의 결과로 나온 소수들의 길이가 소수인 수를 의미한다. 풀이 에라토스테네스 채를 이용해서 A,B사이의 모든 소수들을 구해놓은 후, A,B사이에 있는 임의의 정수 X가 언더프라임인지 확인하는 방식으로 푸는 문제다. 이 때, 시간이 애매할거 같아서, 연산을 빠..
[백준 / 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] 10891 Cactus? Not cactus? (cpp) 문제 출처 : https://www.acmicpc.net/problem/10891 10891번: Cactus? Not cactus? 첫 번째 줄에 그래프의 정점의 개수와 간선의 개수를 나타내는 두 정수 N,M (1 ≤ N,M ≤ 100,000) 이 공백으로 구분되어 주어진다. 다음 M개의 줄에는 간선이 연결하고 있는 두 정점을 나타내는 두 정 www.acmicpc.net 양방향 그래프에서 각 정점에서 시작해 자기 자신으로 돌아오는 사이클이 2개 이상이라면 Cactus가 아니며, 하나 이하라면 Cactus이다. 이 때, 주어진 그래프가 Cactus인지 Not cactus인지 출력하는 문제다. 풀이 처음에는 단절점을 찾고, 단절점에 대해 자식 트리가 2개 이상이라면 Not cactus를 출력하게 해줬는데, ..
[백준 / 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으로 만드는 사각형 범위의 갯수..