본문 바로가기

분류 전체보기

 (340)
[백준 / BOJ] 1719 택배 문제 출처 : www.acmicpc.net/problem/1719 1719번: 택배 첫째 줄에 두 수 n과 m이 빈 칸을 사이에 두고 순서대로 주어진다. n은 집하장의 개수로 200이하의 자연수, m은 집하장간 경로의 개수로 10000이하의 자연수이다. 이어서 한 줄에 하나씩 집하장간 경 www.acmicpc.net n개의 집하장에 택배가있다. 각 집하장에서 다른 집하장으로 이동거리를 최소화하여 택배를 보낼려한다. m개의 집하장 경로와 이동거리가 주어졌을때, 경로표를 만드는 문제다. (경로표는 현재 집하장에서 다른집하장으로 택배를 이동시킬려할때 가장 먼저 거쳐가야할 집하장을 표시한 표이다.) 풀이 플로이드 와샬을 이용해 푸는문제다. dp배열을 pair로 선언해 로 저장해놓는다. 현재 i,j에 저장된 값보..
[백준 / BOJ] 10868 최솟값 문제 출처 : www.acmicpc.net/problem/10868 10868번: 최솟값 N(1 ≤ N ≤ 100,000)개의 정수들이 있을 때, a번째 정수부터 b번째 정수까지 중에서 제일 작은 정수를 찾는 것은 어려운 일이 아니다. 하지만 이와 같은 a, b의 쌍이 M(1 ≤ M ≤ 100,000)개 주어졌을 때는 www.acmicpc.net N개의 숫자들을 입력받고 구간 (a,b)를 M번 입력받는다. 구간 a,b사이에서 가장 작은 값을 출력하는 문제다. 풀이 N과 M이 최대 10만이라 모든경우를 다 봐주면 1억번돌아서 시간초과가 나기때문에, 세그먼트 트리를 이용해서 각 구간을 빠르게 찾아줘야한다. 세그먼트 트리에 각 구간의 최솟값을 저장한다. 예제 1의 경우, 구간 1~10 에서의 최솟값은 5, 구..
[백준 / BOJ] 1162 도로포장 문제 출처 : www.acmicpc.net/problem/1162 1162번: 도로포장 첫 줄에는 도시의 수 N(1 ≤ N ≤ 10,000)과 도로의 수 M(1 ≤ M ≤ 50,000)과 포장할 도로의 수 K(1 ≤ K ≤ 20)가 공백으로 구분되어 주어진다. M개의 줄에 대해 도로를 연결짓는 두 도시와 도로를 통과하 www.acmicpc.net 도시의수 N, 도로의수 M, 포장할 도로의수 K가 주어진다. M개의 도로를 K만큼 포장할수있고, 포장한 도로의 비용은 0이될때, 최소비용을 구하는 문제다. 풀이 2206 벽 부수고 이동하기 와 비슷한 느낌의 문제였다. 다익스트라로 풀었는데, 포장횟수가 20까지밖에 안주어지므로 모든경우를 다 봐줘도 시간초과가 나지않는다. check배열을 2차원으로 만들어서, 체크..
[백준 / BOJ] 1395 스위치 문제 출처 : www.acmicpc.net/problem/1395 1395번: 스위치 첫 줄에는 스위치의 개수 N(2 ≤ N ≤ 100,000)과 처리할 일의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 다음 M개의 줄에 대해 각 줄에 처리할 일에 대한 정보가 담겨진 세 개의 정수 O, Si, Ti가 입력된다. O www.acmicpc.net N개의 스위치가 있고 M번의 명령이 주어진다. 명령은 O,S,T의 형태로 주어지는데, O가 1 이라면, S부터 T까지 켜져있는 전구의 갯수를 구하는 명령이고, O가 0이면, S부터 T까지의 전구의 상태를 반전시키는 명령이다. 풀이 구간 합 구하기 2와 비슷하게 풀리는 문제였다. N이 10만, M이 10만이므로, 한번 업데이트시 최악의경우 10만log10만번 ..
[백준 / BOJ] 10999 구간 합 구하기 2 문제 출처 : www.acmicpc.net/problem/10999 10999번: 구간 합 구하기 2 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)과 M(1 ≤ M ≤ 10,000), K(1 ≤ K ≤ 10,000) 가 주어진다. M은 수의 변경이 일어나는 횟수이고, K는 구간의 합을 구하는 횟수이다. 그리고 둘째 줄부터 N+1번째 줄 www.acmicpc.net 수의 개수 N, M, K가 주어진다. M은 수의 변경이 일어나는 횟수이고, K는 각 구간의 합을 구하는 횟수이다. 앞의 수에 따라서, 변경, 합을 구하면되는데, 1은 변경이고 2는 구간합이다. 예를들어, 1 1 5 10 이 나오면, 1부터 5범위까지 +10을 해주면된다. 풀이 N의 최댓값이 1,000,000이고, M과 K가 각각 1..
[백준 / BOJ] 17087 숨바꼭질 6 문제 출처 : www.acmicpc.net/problem/17087 17087번: 숨바꼭질 6 수빈이는 동생 N명과 숨바꼭질을 하고 있다. 수빈이는 현재 점 S에 있고, 동생은 A1, A2, ..., AN에 있다. 수빈이는 걸어서 이동을 할 수 있다. 수빈이의 위치가 X일때 걷는다면 1초 후에 X+D나 X-D로 이 www.acmicpc.net 수빈이가 동생'들'과 숨바꼭질을한다. 선영이는 +D, -D만큼 이동할수있다. 선영이의 위치와 동생들의 위치가 주어졌을때, 선영이가 모든 동생을 찾을수있는 최대 D값을 찾는문제다. 풀이 수학문제다. 선영이는 모든 동생을 찾아야한다. 선영이는 항상 +D, -D만큼 움직일수있으므로, 모든 동생과의 거리차들의 최대공약수만큼 움직여야 모든동생들을 찾을수있다. 1. 선영이의 ..
[백준 / 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를 칠하기 위해..

티스토리툴바