본문 바로가기

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

 (260)
[백준 / BOJ] 17071 숨바꼭질 5 (1~5) 문제 출처 : www.acmicpc.net/problem/17071 17071번: 숨바꼭질 5 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 500,000)에 있고, 동생은 점 K(0 ≤ K ≤ 500,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 www.acmicpc.net 이 문제는 다른 숨바꼭질 문제들과는 달리, 동생이 매 시간마다 +1 +2 +3 +4 +5 ... 의 속력으로 앞으로 질주한다. 이때, 수빈이가 동생을 찾는 가장 빠른 시간을 출력하는 문제다. 풀이 BFS로 풀리는 문제다. 우선 BFS로 수빈이가 해당 정점에 도달하는 최솟값들을 전부 갱신해주고 동생을 움직이며, 서로가 만날수있는지 봐줬다. (동생이 수빈이를 찾는..
[백준 / BOJ] 1149 RGB거리 문제 출처 : www.acmicpc.net/problem/1149 1149번: RGB거리 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 www.acmicpc.net 집의수 N이 주어진다. 이때, 각 집은 빨강,초록,파랑으로 칠할수있고, 색깔은 연속되게 칠하지못한다. 각 색깔로 칠하기위해 드는 비용이 주어졌을때 최솟값을 구하는 문제다. 풀이 N이 최대 1000이고, 시간제한이 0.5라서 완탐으로 풀경우 시간초과가 난다. Dp를 이용하면 풀리는 문제였다. 각 색깔을 연속으로 칠할수없다는 조건이있다. 즉, 현재 색 R, G, B를 칠하기 위해..
[백준 / BOJ] 15970 화살표 그리기 문제 출처 : www.acmicpc.net/problem/15970 15970번: 화살표 그리기 직선 위에 위치를 나타내는 0, 1, 2, ...와 같은 음수가 아닌 정수들이 일정한 간격으로 오른쪽 방향으로 놓여 있다. 이러한 위치들 중 N개의 위치에 하나씩 점들이 주어진다(). 주어진 점들 www.acmicpc.net 점들의 색깔과 위치(x좌표)가 주어진다. 각각의 점을 가까우면서 같은색깔인 점에 연결할려할때, 연결한 선의 최대거리를 구하는 문제다. 풀이 N이 크지않아 완전탐색으로도 풀리는문제다. 문제를 잘 읽지않고 점들의 색깔이 항상 2개인줄 알고풀다가 몇번 틀렸었다. 1. 점들을 입력받을때, 같은 색깔은 같은 벡터에 들어가도록 입력받는다. 2. 각 벡터를 N번 정렬한다. 3. 현재 점의 idx에서 ..
[백준 / BOJ] 8982 수족관 1 문제 출처 : www.acmicpc.net/problem/8982 8982번: 수족관 1 입력의 첫 줄은 수족관의 경계에 있는 꼭짓점의 개수 N(1 ≤ N ≤ 5,000)이 주어진다. N은 짝수이다. 수족관의 경계는 항상 꼭짓점 (0, 0)부터 시작한다. 그리고 마지막 꼭짓점은 (A, 0)의 형태로 끝난 www.acmicpc.net 물이 들어있는 수족관이있다. 수족관의 바닥에 구멍이 뚫려있을때, 각 구멍을통해 빠져나간후 남은 물의 양을 구하는 문제다. 풀이 범위가 크지않아 완전탐색으로도 풀리는 문제다. 각 구멍의 좌표를 기준으로 왼쪽, 오른쪽으로 탐색하며 현재의 높이보다 수족관의 바닥의 높이가 높을경우, 높이를 올려주며 남아있는 물의 양을 구해주면된다. 1. 구멍이 있는 바닥의 x1(시작 x 좌표) 부터..
[백준 / BOJ] 2495 연속구간 문제 출처 : www.acmicpc.net/problem/2495 2495번: 연속구간 여덟 자리의 양의 정수가 주어질 때, 그 안에서 연속하여 같은 숫자가 나오는 것이 없으면 1을 출력하고, 있으면 같은 숫자가 연속해서 나오는 구간 중 가장 긴 것의 길이를 출력하는 프로그램을 www.acmicpc.net 여덟자리 정수가 주어졌을때, 연속해서 나오는 정수들의 최대 갯수를 구하면된다. 풀이 입력받고 연속해서 나오는 정수들의 최대갯수를 구하면 된다. 정수로 입력받고 한자리씩 짤라가며 해도 되지만, String을 사용하면 훨씬 편하게 할수있다. 소스코드 https://github.com/devxb/JJUNalgo/blob/master/2495%20%EC%97%B0%EC%86%8D%EA%B5%AC%EA%B0%8..
[백준 / BOJ] 1516 게임 개발 문제 출처 : www.acmicpc.net/problem/1516 1516번: 게임 개발 첫째 줄에 건물의 종류 수 N(1 ≤ N ≤ 500)이 주어진다. 다음 N개의 줄에는 각 건물을 짓는데 걸리는 시간과 그 건물을 짓기 위해 먼저 지어져야 하는 건물들의 번호가 주어진다. 건물의 번호는 1부 www.acmicpc.net N개의 건물이 주어지고, 각 건물을 짓는 시간과 그 건물을 짓기위해 먼저 지어야할 건물들이 주어진다. 이때 각 건물을 짓기 위해 필요한 최소 시간을 구하는 문제다. (각 건물은 동시에 지을수있다.) 풀이 N의 최댓값이 500이라 완전탐색을 하게되면, 최악의경우 501^2*250 만큼 돌아서 시간초과가 난다. DP로 풀리는 문제였다. 각 건물을 짓기위해 지어야할 선행건물들을 모두 지었다면..
[백준 / BOJ] 1082 방 번호 문제 출처 : www.acmicpc.net/problem/1082 1082번: 방 번호 문방구에서 파는 숫자의 개수 N이 주어진다. N은 10보다 작거나 같은 자연수이다. 문방구에서 파는 숫자는 0보다 크거나 같고, N-1보다 작거나 같은 자연수이다. 예를 들어, N=4이면, 문방구에서 파 www.acmicpc.net 갖고있는돈이 주어지고, 각 숫자들의 가격이주어진다 (0~9번까지숫자들의 가격) 이때, 숫자들을 조합해서만들수있는 최댓값을 찾는 문제다. 예를들어, 예제 1의경우, 순서대로 숫자 2를 8원에사고 숫자 1을 7원에 , 숫자 0을 6원에사면, 총 21원으로 210이 만들어지고 이때 최댓값을 갖는다. 풀이 완전탐색으로 풀경우, 최악의 경우, 총 10개의 글자가 중복을 허용해서 50개의 자리에 올수..
[백준 / BOJ] 1083 소트 문제 출처 : www.acmicpc.net/problem/1083 1083번: 소트 크기가 N인 배열 A가 있다. 배열에 있는 모든 수는 서로 다르다. 이 배열을 소트할 때, 연속된 두 개의 원소만 교환할 수 있다. 그리고, 교환은 많아봐야 S번 할 수 있다. 이때, 소트한 결과가 사전 www.acmicpc.net N크기의 정수배열과 S가 주어졌을때, 정수들의 순서를 최대 S번 바꿔서 사전순으로 가장 뒤에있는 것을 출력하는 문제다. 예를들어, 5 10 20 30 40 50 5 는 50 20 10 30 40 이 출력되어야한다. 풀이 그리디로 풀리는 문제였다. 사전순으로 가장 뒤에있는단어는 1. 앞에있는 단어가 뒤에있는 단어보다 클수록 사전순으로 앞선다. 이런 조건이있다. 따라서, 현재 위치에서 S번 뒤로 ..

티스토리툴바