본문 바로가기

분류 전체보기

 (191)
배열에서 이동( BOJ 1981 ) 문제 : https://www.acmicpc.net/problem/1981 1981번: 배열에서 이동 n×n짜리의 배열이 하나 있다. 이 배열의 (1, 1)에서 (n, n)까지 이동하려고 한다. 이동할 때는 상, 하, 좌, 우의 네 인접한 칸으로만 이동할 수 있다. 이와 같이 이동하다 보면, 배열에서 몇 개의 수를 www.acmicpc.net 문제 파악하기 (1, 1)에서 (N, N)까지 이동하는 모든 경우 중 (최댓값-최솟값)이 가장 작은 경우를 구하는 문제입니다. 상하좌우 모든 방향으로 이동할 수 있으며, 100*100크기의 배열이기 때문에 모든 경우의 수를 구하는 건 불가능합니다. 그렇기에 적절하게 탐색의 범위를 조절해야 합니다. 문제 해결하기 문제를 해결하기 위해서는 (1, 1)에서 (N, N)까..
전구 끄기( BOJ 14927 ) 문제 : https://www.acmicpc.net/problem/14927 14927번: 전구 끄기 홍익이는 N x N 전구 판을 가지고 있다. 전구 판에는 각 칸마다 전구가 하나씩 연결되어 있다. 이 전구 판에서 하나의 전구를 누르면, 해당 전구를 포함하여 상하좌우의 총 5개 전구들의 상태가 변 www.acmicpc.net 문제 파악하기 불 켜진 전구를 효율적으로 끄는 방법을 찾는 문제입니다. 전구를 끄는 문제는 전통적으로 주변 전구들이 함께 영향을 받았는데 이번 문제 역시 하나의 전구를 작동시키면 주변 4방향(동서남북)의 전구 또한 영향을 받는 문제입니다. 이 문제를 해결하기 위해서는 전체적인 전구 상태를 보기 보다는 한 줄씩 나눠서 전구들을 확인해야 합니다. 문제 해결하기 우선, 전구는 항상 1번..
파일 합치기 3 문제 : https://www.acmicpc.net/problem/13975 13975번: 파일 합치기 3 프로그램은 표준 입력에서 입력 데이터를 받는다. 프로그램의 입력은 T개의 테스트 데이터로 이루어져 있는데, T는 입력의 맨 첫 줄에 주어진다.각 테스트 데이터는 두 개의 행으로 주어지는데, www.acmicpc.net 문제 파악하기 K개의 파일을 합쳐서 하나의 소설로 만들 때, 필요한 최소비용을 구하는 문제입니다. 이전 문제와 다른 점은 파일을 합칠 때, 연속하지 않은 파일 2개를 선택할 수 있다는 것입니다. 이전 문제는 항상 연속된 파일 2개를 선택해야 했지만 지금은 파일 2개의 위치가 어디있든 상관없이 하나의 파일로 합칠 수 있습니다. 그렇기에 이 문제는 단순하게 생각할 수 있습니다. 문제 해결..
효율적으로 소 사기( BOJ 5896 ) 문제 : https://www.acmicpc.net/problem/5896 5896번: 효율적으로 소 사기 첫 번째 줄에 소 시장에 나온 소들의 마릿수 N(1 ≤ N ≤ 50,000), 농부 존이 가지고 있는 쿠폰의 개수 K(1 ≤ K ≤ N), 농부 존이 가지고 있는 돈 M(1 ≤ M ≤ 1014)이 주어진다. 다음 줄부터 Pi (1 ≤ Pi ≤ www.acmicpc.net 문제 파악하기 농부 존이 구매할 수 있는 소의 최대 개수를 구하는 문제입니다. 소는 일반 가격으로 구매할 수도 있고, 쿠폰을 사용하여 구매할 수도 있으며, 쿠폰을 구매하는 소의 가격은 일반 가격보다 같거나 저렴합니다. 주어지는 소의 개수는 최대 50,000 마리이기 때문에 우리는 최소한 시간 복잡도가 O(NlogN) 이하인 알고리즘..
Rook Path( Atcoder 232-E ) 문제 : https://atcoder.jp/contests/abc232/tasks/abc232_e E - Rook Path AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online. atcoder.jp 문제 파악하기 (x1, y1)에 위치한 룩(Rook)을 K번 움직여서 (x2, y2)에 도달하게 만드는 방법의 수를 구하는 문제입니다. 룩은 현재 위치에서 가로/세로 방향으로 어디든 갈 수 있으며, 주어지는 체스판의 넓이(109*109)와 움직일 수 있는 횟수(106)을 본다면 완전탐색을 통해 모든 경우의 수를 구하기는 힘들다는 걸 알 수 있습니다. 그..
여우가 정보섬에 올라온 이유( BOJ 17131 ) 문제 : https://www.acmicpc.net/problem/17131 17131번: 여우가 정보섬에 올라온 이유 첫 줄에 별의 개수 N이 주어진다. 그 다음 줄부터 N개의 줄에 걸쳐 별의 좌표 x y가 주어진다. www.acmicpc.net 문제 파악하기 제시된 별들의 중 V형 별자리를 만들 수 있는 모든 경우의 수를 구하는 문제입니다. V형 별자리이라는 건 세 별 (s,t,u)가 s.x t.y < u.y이면 V형 별자리라고 합니다. 결국 우리는 t보다 높은 위치에 있는 s와 u를 각각 왼쪽과 오른쪽에서 찾아야 합니다. 왼쪽에서 찾을 수 있는 s의 개수와 오른쪽에서 찾을 수 있는 u의 개수를 찾은 다음, 서로 곱해주면 t로 만들 수 있는 V형 별자리의 개수가 나..
수상 택시( BOJ 2836 ) 문제 : https://www.acmicpc.net/problem/2836 2836번: 수상 택시 상근이가 살고 있는 도시에는 큰 강이 흐르고 있고, 모든 사람의 집은 이 강 근처에 있다. 집은 0번부터 M번까지 강을 따라서 번호가 매겨져 있고, 인접한 집 사이의 거리는 모두 1 킬로미터이다. www.acmicpc.net 문제 파악하기 상근이가 0번에서 M번으로 이동하면서 N명의 사람들을 목적지까지 태워주는데 필요한 최소 이동거리를 구하는 문제입니다. N명의 사람들은 항상 0번 ~ M번 사이의 위치에서 이동한다는 점에 초점을 맞추면 문제를 쉽게 해결할 수 있습니다. 상근이는 가장 오른쪽 위치인 M번으로 이동해야 하기 때문에 오른쪽으로 이동하는 사람(ex. 1 > 3으로 이동)은 신경쓸 필요 없습니다. 우..
Simple Operations on Sequence( Atcoder 232-F ) 문제 : https://atcoder.jp/contests/abc232/tasks/abc232_f F - Simple Operations on Sequence AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online. atcoder.jp 문제 파악하기 N개의 숫자로 이루어진 A 수열의 값을 변경하여 B 수열과 동일하게 만드는데 필요한 최소 비용을 구하는 문제입니다. 우리는 다음 2가지 작업을 통해 A 수열의 값을 바꿀 수 있습니다. (1) X만큼의 비용을 들어 Ai의 값 1 증가/감소 시키기 (2) Y만큼의 비용을 들어 Ai의 값과 Ai+1의 값 교환..

티스토리툴바