본문 바로가기

문제 노트

 (155)
카드 바꾸기( BOJ 25401 ) 문제 : https://www.acmicpc.net/problem/25401 25401번: 카드 바꾸기 $N$개의 카드가 놓여있다. 편의상 가장 왼쪽에 있는 카드를 $1$번 카드, 그 다음에 있는 카드를 $2$번 카드 $\dots$, 가장 오른쪽에 있는 카드가 $N$번 카드라고 하자. $N$개의 카드에는 각각 정수가 하 www.acmicpc.net 문제 파악하기 N개의 카드를 등차수열로 만드는 문제입니다. 공차는 음수, 0, 양수 모두 될 수 있으며, 주어진 N개의 숫자 중 일부분을 바꿔 등차수열로 만들었을 때, 바꾼 카드 수의 최솟값을 구해야 합니다. 등차 수열을 만드는 가장 간단한 방법은 모든 숫자를 하나의 숫자로 통일하는 것입니다. 하지만 이 방법은 비효율적이기에 조금 더 효율적인 방법이 필요하며,..
조약돌( BOJ 25378 ) 문제 : https://www.acmicpc.net/problem/25378 25378번: 조약돌 좌우 한 줄로 있는 N개의 장소 각각에 조약돌이 몇 개씩 놓여 있다. 철수가 할 수 있는 작업의 종류는 아래 두 가지이다. 인접한 두 장소에서 임의의 동일한 개수의 조약돌을 가져가기 한 장소에 www.acmicpc.net 문제 파악하기 N개의 장소에 놓여진 조약돌을 2개의 작업으로 모두 가져오는 최소 횟수를 구하는 문제입니다. 두 작업은 임의의 개수를 가져올 수 있다고 했으나, 작업의 횟수를 최소로 해야하기 때문에 보통 하나 이상의 장소에 있는 모든 조약돌을 가져오는 작업이라고 할 수 있습니다. 아쉽게도 각 장소에 놓인 조약돌의 개수가 최대 108개이기 때문에 단순한 재귀함수 및 메모이제이션으로 해결할 수 ..
네온 사인( BOJ 8907 ) 문제 : https://www.acmicpc.net/problem/8907 8907번: 네온 사인 첫째 줄에는 테스트 케이스의 수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 꼭짓점의 개수 N(3 ≤ N ≤ 1,000)이 주어진다. 다음 N-1개의 각 야광 튜브의 색이 주어진다. 이 줄의 i번째 줄에는 꼭 www.acmicpc.net 문제 파악하기 N개의 꼭지점 중 3개의 꼭지점을 골라 삼각형을 만들었을 때, 모든 간선의 색이 동일한 경우의 수를 구하는 문제입니다. N이 최대 1,000이기 때문에 처음 보면 크지 않아 보이지만, 1000개의 정점 중 3개의 정점을 선택할 수 있는 경우의 수는 대략 1.6억 가지 경우의 수가 있습니다. 어마어마한 경우의 수이며, 이정도 규모라면 컴퓨터도 1초 안에 모든..
전구와 스위치( BOJ 2138 ) 문제 : https://www.acmicpc.net/problem/2138 2138번: 전구와 스위치 N개의 스위치와 N개의 전구가 있다. 각각의 전구는 켜져 있는 상태와 꺼져 있는 상태 중 하나의 상태를 가진다. i(1 < i < N)번 스위치를 누르면 i-1, i, i+1의 세 개의 전구의 상태가 바뀐다. 즉, 꺼져 www.acmicpc.net 문제 파악하기 입력된 N개의 스위치를 적절하게 눌러서 우리가 원하는 상태로 바꿀 수 있는지, 만약 바꿀 수 있다면 눌러야 하는 스위치의 최소 횟수를 구하는 문제입니다. 만약 N의 값이 작다면 직접 모든 경우의 수를 확인할 수 있지만 N이 최대 100,000이기 때문에 좀 더 효율적인 알고리즘이 필요합니다. 다행히 스위치는 항상 바로 왼쪽과 오른쪽에 위치한 전구..
RPG( BOJ 1315 ) 문제 : https://www.acmicpc.net/problem/1315 1315번: RPG 준규는 새 RPG 게임을 시작했다. 이 게임에서 캐릭터는 2가지 스탯을 가지고 있다. 하나는 힘(STR)이고, 다른 하나는 지력(INT)이다. 캐릭터를 생성했을 때, 두 스탯은 모두 1이다. 게임에는 총 N개의 www.acmicpc.net 문제 파악하기 경험치를 힘(STR)과 지력(INT)에 적절히 투자해서 클리어할 수 있는 퀘스트의 최댓값을 구하는 문제입니다. 각각의 퀘스트는 클리어를 할 수 있는 힘과 지력의 제한이 있으며, 캐릭터의 힘과 지력 중 어느 한 곳의 능력치가 특정 퀘스트의 힘과 지력 제한보다 크거나 같다면 해당 퀘스트를 클리어하고 경험치를 얻을 수 있습니다. 문제를 해결할 수 있는 가장 단순한 알..
복구( BOJ 15908 ) 문제 : https://www.acmicpc.net/problem/15908 15908번: 복구 예제 1에 대해, 3번째 수와 6번째 수를 지우면 {3, 1, 2}, {2, 1}, {3, 1, 3}이 된다. 예제 2에 대해, 1번째, 8번째, 9번째, 11번째, 16번째, 17번째, 19번째 수를 지우면 {4, 2, 5, 5}, {5, 1, 4, 5, 1}, {4, 2, 5, 2}가 된다 www.acmicpc.net 문제 파악하기 N개의 숫자(사용자 데이터)를 적절하게 지워서 조건에 맞는 사용자 데이터를 만드는 경우의 수 중, 지운 숫자들이 가진 가능성의 최댓값을 가장 작게 만드는 경우를 구하는 문제입니다. 단순히 숫자를 지우기에는 100,000개의 데이터가 너무 많기에 문제를 좀 더 단순화 시킬 필요가..
창고 다각형( BOJ 2304 ) 문제 : https://www.acmicpc.net/problem/2304 2304번: 창고 다각형 첫 줄에는 기둥의 개수를 나타내는 정수 N이 주어진다. N은 1 이상 1,000 이하이다. 그 다음 N 개의 줄에는 각 줄에 각 기둥의 왼쪽 면의 위치를 나타내는 정수 L과 높이를 나타내는 정수 H가 한 개의 www.acmicpc.net 문제 파악하기 주어진 막대 기둥을 둘러싸는 가장 작은 창고 다각형의 크기를 구하는 문제입니다. 주어진 입력의 범위가 크지 않기 때문에 어렵지 않게 해결할 수 있는 문제입니다. 이 문제에서 가장 중요한 점은 가장 높은 막대의 위치입니다. 가장 높은 막대의 위치를 기준으로 나눠서 생각해보면 쉽게 해결할 수 있습니다. 문제 해결하기 지붕을 오목하게 만들지 않으면서 창고 다각형의..
변신 이동 게임( BOJ 15906 ) 문제 : https://www.acmicpc.net/problem/15906 15906번: 변신 이동 게임 첫 줄에 2차원 격자의 크기 N(1≤ N ≤ 500), 일반 모드에서 변신 모드로 변신하는 데 소모되는 턴의 수 t(0 ≤ t ≤ 500), 목표 지점의 행과 열의 번호 r(1 ≤ r ≤ N), c(1 ≤ c ≤ N)가 주어진다. 다음 줄에 www.acmicpc.net 문제 파악하기 게임 속 캐릭터를 (1, 1)에서 (r, c)까지 이동하는데 필요한 최소 턴 횟수를 구하는 문제입니다. 캐릭터는 1턴을 사용하여 상하좌우 인접한 1칸으로 움직이거나 t턴을 사용하여 변신 모드로 변신한 다음, 1턴을 사용하여 상하좌우 방향의 가장 가까운 워프 지점('#')으로 이동할 수 있습니다. 각각의 칸에서 이동할 수..

티스토리툴바