본문 바로가기

분류 전체보기

 (189)
아이템 획득( BOJ 28216 ) 문제 : https://www.acmicpc.net/problem/28216 28216번: 아이템 획득 $N ≤ 2\,000$, $Q ≤ 2\,000$, $x_i ≤ 1\,000$, $y_i ≤ 1\,000$, $w_i ≤ 10$, 매 순간 자동차의 $x$, $y$좌표는 $1\,000$ 이하이다. www.acmicpc.net 문제 파악하기 자동차가 Q번 이동하면서 획득한 상자의 아이템 개수를 구하는 문제입니다. 자동차는 (1, 1) 위치에서 시작하며, 이동하면서 만나는 상자에서 항상 아이템을 얻을 수 있습니다. 상자와 이동하는 횟수 모두 최대 200,000번이기에 전탐색으로는 문제를 해결할 수 없습니다. 하지만 x와 y의 값이 최대 200,000이라는 범위 안이기 때문에 x와 y축을 기준으로 적절하게 상..
0과 1( BOJ 8111 ) 문제 : https://www.acmicpc.net/problem/8111 8111번: 0과 1 각각의 테스트 케이스마다 N의 배수이면서, 구사과가 좋아하는 수를 아무거나 출력한다. 만약, 그러한 수가 없다면 BRAK을 출력한다. www.acmicpc.net 문제 파악하기 0과 1로 이루어졌으며 길이가 100 이하인 숫자 중 N의 배수를 구하는 문제입니다. 최대 길이가 정해져있지만 모든 경우를 확인하기에는 2100이라는 경우의 수는 너무 많습니다. 그렇기에 굳이 확인할 필요가 없는 숫자는 확인하지 않아도 되며, 이 때 사용할 수 있는 도구는 바로 나머지 연산입니다. 문제 해결하기 나머지 연산을 어떻게 활용하면 불필요한 탐색을 제거할 수 있을까요? 우리가 사용하는 숫자는 0과 1이며 나누는 숫자는 항상 N..
주유소( BOJ 28219 ) 문제 : https://www.acmicpc.net/problem/28219 28219번: 주유소 KOI 국가는 $N$개의 마을로 이루어져 있다. 각 마을에는 $1$번 마을, $2$번 마을, $\cdots$, $N$번 마을과 같이 번호가 붙어 있다. 그리고 도로가 $N - 1$개 있는데, 각각의 도로는 서로 다른 두 마을을 잇 www.acmicpc.net 문제 파악하기 N개의 마을에 필요한 주유소의 최소 개수를 구하는 문제입니다. N개의 마을은 (N-1)개의 도로로 연결되어 있으며, 길이가 K인 두 마을 사이의 경로에는 꼭 1개 이상의 주유소가 있어야 합니다. 문제 설명에서 (N-1)개의 도로로 연결되어 있으며, 모든 마을 사이의 경로는 유일하게 존재한다는 점을 통해 N개의 마을은 트리 형태로 연결되어 ..
좋은 수( BOJ 5624 ) 문제 : https://www.acmicpc.net/problem/5624 5624번: 좋은 수 정수 N개로 이루어진 수열 A가 있다. 이때, i번째 수가 그 앞에 있는 수 세 개의 합으로 나타낼 수 있을 때, 그 수를 좋다고 한다. (같은 위치에 있는 수를 여러 번 더해도 된다) 수열이 주어졌을 때 www.acmicpc.net 문제 파악하기 N개의 정수 중 자신보다 앞에 있는(왼쪽에 위치한) 3개의 숫자들의 합으로 나타낼 수 있는 숫자의 개수를 구하는 문제입니다. N의 범위가 최대 5,000이기 때문에 3개의 숫자를 모두 확인할 수는 없습니다. 맨 첫 번째 숫자부터 하나씩 배열에 체크하면서 각각의 숫자를 만들 수 있는지 여부를 체크하면 되며, 이 경우 동적 프로그래밍 기법을 활용할 수 있습니다. 문제 ..
Swapity Swapity Swap( BOJ 18783 ) 문제 : https://www.acmicpc.net/problem/18783 18783번: Swapity Swapity Swap Initially, the order of the cows is $[1,2,3,4,5,6,7]$ from left to right. After the first step of the process, the order is $[1,5,4,3,2,6,7]$. After the second step of the process, the order is $[1,5,7,6,2,3,4]$. Repeating both steps a second time yields t www.acmicpc.net 문제 파악하기 모든 운동이 끝났을 때, N마리 소들의 배치를 출력하는 문제입니다. 소들은 M개의..
타일 코드( BOJ 1720 ) 문제 : https://www.acmicpc.net/problem/1720 1720번: 타일 코드 2×N 크기의 넓은 판을 1×2 (또는 2×1) 크기와 2×2 크기의 타일로 채우려고 한다. 여러 가지 경우가 있을 수 있으므로, 각각을 하나의 코드로 대응시켜서 암호화에 이용하려고 한다. 그런데 문제가 www.acmicpc.net 문제 파악하기 2*N 크기의 판을 1*2 타일과 2*2 타일을 사용하여 채우는 방법 중 대칭인 경우는 1번으로 카운트하여 모든 경우의 수를 구하는 문제입니다. 여기서 대칭이라는 건 문제의 예시와 같이 뒤집었을 때 동일한 모양을 가지고 있는 경우를 의미합니다. 기본적으로 타일 문제들은 이전에 구한 가짓수를 활용하며, 이 문제 역시 이전에 구한 가짓수를 활용하여 현재 타일(N)까지 ..
요세푸스 문제 2( BOJ 1168 ) 문제 : https://www.acmicpc.net/problem/1168 1168번: 요세푸스 문제 2 첫째 줄에 N과 K가 빈 칸을 사이에 두고 순서대로 주어진다. (1 ≤ K ≤ N ≤ 100,000) www.acmicpc.net 문제 파악하기 요세푸스 수열을 빠르게 구하는 문제입니다. 이전 문제(요세푸스 문제)와 다른 점은 N의 크기가 100,000으로 늘어났으며, 시간 제한도 0.15초로 줄어들었습니다. 그래서 이전 문제에서 사용한 알고리즘인 큐(배열)을 활용한 전탐색(브루트포스) 알고리즘으로는 해결할 수 없습니다. 문제를 해결하기 위해서는 다음 숫자를 좀 더 빠르게 찾아야하며, 여기서 자료구조를 활용하면 문제를 해결할 수 있습니다. 문제 해결하기 문제를 해결하기 위해서는 순열의 다음 숫자를 빠..
레벨 업( BOJ 25405 ) 문제 : https://www.acmicpc.net/problem/25405 25405번: 레벨 업 여러분은 $N$명의 게임 캐릭터를 육성하려고 한다. $i$ ($1 ≤ i ≤ N$) 번째 캐릭터의 현재 레벨은 $L_i$이다. 캐릭터의 레벨을 올리기 위해 아래와 같은 트레이닝을 총 $M$번 진행할 것이다. 레벨이 www.acmicpc.net 문제 파악하기 N개의 캐릭터를 조건에 맞게 레벨업 시켰을 때의 결과를 출력하는 문제입니다. 캐릭터는 K개의 캐릭터를 동시에 1씩 레벨업 할 수 있으며, 총 M번 레벨업시킬 수 있습니다. N과 M의 범위에 따라 해결할 수 있는 방식과 난이도가 달라지는 문제로, 전체 문제를 해결하기 위해서는 레벨이 올라가는 특징을 적절하게 캐치해야 합니다. 문제 해결하기 그렇다면 문제를..

티스토리툴바