본문 바로가기

알고리즘 (2020 : 08 : 10 ~ )

 (260)
[백준 / 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] 1153 네 개의 소수 (Java) 문제 출처 : https://www.acmicpc.net/problem/1153 1153번: 네 개의 소수 임의의 자연수가 주어지면, 이를 네 개의 소수의 합으로 분해하는 프로그램을 작성하시오. 예를 들어 38 = 5 + 7 + 13 + 13이 된다. www.acmicpc.net 1
[백준 / BOJ] 19585 전설 (cpp / Java) 문제 출처 : https://www.acmicpc.net/problem/19585 19585번: 전설 Sogang ICPC Team에는 색상 이름과 닉네임의 순서로 이여서 팀명을 지으면 ICPC 리저널에서 수상할 수 있다는 전설이 있다. 색상 이름들과 닉네임들이 주어질 때, Q개의 팀에 대해 다음 리저널에서 수 www.acmicpc.net C개의 색상, N개의 닉네임, Q개의 팀이 주어진다. 이때, Q개의 팀중 색상+닉네임 으로 이루어진 팀은 "Yes" 아닌경우 "No"를 출력하는 문제다. 풀이 Trie + 해싱 알고리즘으로 푼 문제다. 색상과 닉네임을 모두 Trie구조로 만들경우, 색상의 최대길이 * 닉네임의 최대길이 * 팀의 최대 갯수 = 1000 * 1000 * 20000이 되어서 TLE가 나온다...
[백준 / 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] 2251 물통 (cpp) 문제 출처 : https://www.acmicpc.net/problem/2251 2251번: 물통 각각 부피가 A, B, C(1≤A, B, C≤200) 리터인 세 개의 물통이 있다. 처음에는 앞의 두 물통은 비어 있고, 세 번째 물통은 가득(C 리터) 차 있다. 이제 어떤 물통에 들어있는 물을 다른 물통으로 쏟아 부 www.acmicpc.net 각각 부피가 A, B, C인 물통이 있고 A, B는 비어있으며 C는 꽉 차있다. 물을 이동 시킬때는 항상 하나의 물통이 꽉차거나 빌때까지만 옮길 수 있다. 이때, 물통 A가 비어있을때, 물통 C에 있을수 있는 물의 양을 모두 구하는 문제다. 풀이 DFS로 풀어도 풀리는 문제다. A, B, C의 최대 용량이 각각 200이므로, 3차원 체크 배열로 이미 방문한 상태를..
[백준 / BOJ] 20010 악덕 영주 혜유 (Java) 문제 출처 : https://www.acmicpc.net/problem/20010 20010번: 악덕 영주 혜유 FT온라인 게임에서 치열한 경쟁을 통해 영주가 된 혜유는 퀘스트를 받았다. 퀘스트의 내용은 자신이 관리하고 있는 마을 사이에 교역로를 건설하여 마을 간 교류를 활성화시키는 것이다. 이때, www.acmicpc.net N개의 마을과 마을을 연결하는 K개의 간선이 주어진다. 이때, K개의 간선을 이용해서 모든 마을을 연결하는 최소비용과 이때 마을사이를 연결하는 거리의 최댓값을 구하는 문제이다. 풀이 최소스패닝트리 알고리즘과 트리의 지름을 구하는 알고리즘을 각각 사용해서 푸는 문제다. 두 알고리즘을 섞어서 사용할 필요는 없고, "모든 마을을 연결하는 최소비용"을 MST를 이용해서 구한후, MST를 ..
[백준 / BOJ] 17615 볼 모으기 문제 출처 : https://www.acmicpc.net/problem/17615 17615번: 볼 모으기 첫 번째 줄에는 볼의 총 개수 N이 주어진다. (1 ≤ N ≤ 500,000) 다음 줄에는 볼의 색깔을 나타내는 문자 R(빨간색 볼) 또는 B(파란색 볼)가 공백 없이 주어진다. 문자열에는 R 또는 B 중 한 종류만 주 www.acmicpc.net 빨간색과 파란색으로 이루어진 N개의 연속된 공이 주어진다. 자신의 옆에 다른색의 공이 있다면, 바로 옆에있는 다른색의 공과 같은 색으로 이루어진 공의 집단을 한번에 뛰어넘을수있을때, 최소한의 이동횟수로 같은색 공끼리 모으는 문제다. 단, 공은 처음으로 움직인 공과 같은색의 공만 조작할 수 있다. 풀이 그리디 문제였다. N이 500,000이라서 어려워 보이..

티스토리툴바