본문 바로가기

문제 노트

 (155)
좋은 수( 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)까지 ..
레벨 업( 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의 범위에 따라 해결할 수 있는 방식과 난이도가 달라지는 문제로, 전체 문제를 해결하기 위해서는 레벨이 올라가는 특징을 적절하게 캐치해야 합니다. 문제 해결하기 그렇다면 문제를..
햄최몇?( BOJ 19645 ) 문제 : https://www.acmicpc.net/problem/19645 19645번: 햄최몇? 세 모질이들 관우, 철환, 길원이가 모였다. 모질이들은 모이면 서로 '햄버거 최대 몇 개 드실 수 있나요?'의 준말인 '햄최몇?'을 시전하며 자랑을 하기 바쁘다. 막내 길원이는 문득 중요한 사실을 www.acmicpc.net 문제 파악하기 3명의 사람이 N개의 햄버거를 나누어먹을 때, 가장 적은 효용을 얻게 되는 사람의 최댓값을 구하는 문제입니다. 효용은 햄버거를 먹으면 얻게 되며, 햄버거는 한 사람이 무조건 다 먹어야 하기 때문에 단순히 3등분 하는 방법으로는 구할 수 없습니다. 따라서, 이 경우에는 효율적으로 가능한 경우를 탐색해야 합니다. 가장 단순하게 재귀 함수를 사용하는 방법부터 배열을 사용하는 ..
행운쿠키 제작소( BOJ 10982 ) 문제 : https://www.acmicpc.net/problem/10982 10982번: 행운쿠키 제작소 데브베이커리에서는 기념일을 맞아 직원들에게 행운쿠키를 선물하기로 하였다. 회사의 간식을 담당하는 철수는 나누어줄 행운 쿠키를 준비하는 역할을 맡게 되었다. 행운쿠키를 만들기 위해서 www.acmicpc.net 문제 파악하기 2개의 오븐을 사용해 모든 행운쿠키를 굽는데 걸리는 최소 시간을 구하는 문제입니다. 쿠키는 어떤 오븐에서 굽는지에 따라 완료되는 시간이 다르기에 쿠키마다 오븐을 적절하게 활용해야 효율적으로 모든 쿠키를 구울 수 있습니다. 전형적인 배낭 문제의 한 종류로, 동적 프로그래밍 기법을 활용하면 어렵지 않게 문제를 해결할 수 있습니다. 문제 해결하기 이 문제에서 중점으로 봐야할 핵심요소는..
Two Machines( BOJ 17528 ) 문제 : https://www.acmicpc.net/problem/17528 17528번: Two Machines 스케줄링 최적화 회사인 SOPT 에 완료해야 할 n개의 작업 t1, t2, ..., tn 이 있다. SOPT 회사는 두 대의 머신 A 와 B 를 보유하고 있다. 각 작업 ti를 완료하기 위해 SOPT 는 머신 A 와 B 둘 중에 오직 하나 www.acmicpc.net 문제 파악하기 2개의 머신(A, B)을 사용하여 N개의 작업을 모두 처리하는데 필요한 시간의 최솟값을 구하는 문제입니다. 각각의 작업은 A와 B 머신 중 하나의 머신에서만 처리될 수 있으며, 선택한 머신에 따라 Ai 또는 Bi만큼의 시간이 소요됩니다. 알고리즘을 단순히 생각하면 두 머신 중 적은 시간이 걸리는 머신에 할당하면 ..
방 청소( BOJ 9938 ) 문제 : https://www.acmicpc.net/problem/9938 9938번: 방 청소 처음 6개의 술은 규칙 1에 의해서 1, 3, 5, 7, 9, 2번 서랍에 보관할 수 있다. 7번째 술은 규칙 3을 적용할 수 있다. 1번 서랍에 들어있는 술을 2로, 2번 서랍에 들어있는 술을 3으로, 3번 서랍에 들어있 www.acmicpc.net 문제 파악하기 N개의 술병을 서랍에 넣을 수 있는지 확인하는 문제입니다. 술병은 각각 정해진 2개의 서랍(A, B) 중 비어있는 위치에 넣을 수 있으며, 이미 서랍에 들어있는 술병을 연쇄로 이동하여 빈 자리가 생기게 만들 수도 있습니다. 다만 술병을 넣는 서랍은 우선순위가 있는데 A와 B 중 비어있는 서랍에 우선적으로 넣어야 하며, 두 서랍에 모두 넣을 수 있다..

티스토리툴바