예민한 블로그

문제 링크https://www.acmicpc.net/problem/3711서론t개의 테스트 케이스가 제공된다. (t에 대한 조건 없음)각 테스트 케이스에서는 G개의 정수를 입력받는다. (1 ≤ G ≤ 300)입력받는 G개의 정수 A1, A2, ... Ag-1, Ag에 대한 조건은 0 ≤ A{i}  G개의 정수들을 k로 나눈 나머지가 모두 다르게 만드는, 가장 작은 k를 찾는 문제였다.먼저 떠올린 풀이는 for(int k = 1;is_equal_exist(k); k++)을 따르는 풀이다. 이러한 풀이를 적용한 예시를 들어보면 다음과 같다.G = 3, A = {2, 5, 7}일 경우 정답이 어떻게 될까?k = 1일 때 나머지는 0, 0, 0이므로 성립하지 않는다.k = 2일 때 나머지는 0, 1, 1이므로 ..

문제 링크https://www.acmicpc.net/problem/2056문제수행해야 할 작업 N개 (3 ≤ N ≤ 10000)가 있다. 각각의 작업마다 걸리는 시간(1 ≤ 시간 ≤ 100)이 정수로 주어진다.몇몇 작업들 사이에는 선행 관계라는 게 있어서, 어떤 작업을 수행하기 위해 반드시 먼저 완료되어야 할 작업들이 있다. 이 작업들은 번호가 아주 예쁘게 매겨져 있어서, K번 작업에 대해 선행 관계에 있는(즉, K번 작업을 시작하기 전에 반드시 먼저 완료되어야 하는) 작업들의 번호는 모두 1 이상 (K-1) 이하이다. 작업들 중에는, 그것에 대해 선행 관계에 있는 작업이 하나도 없는 작업이 반드시 하나 이상 존재한다. (1번 작업이 항상 그러하다)모든 작업을 완료하기 위해 필요한 최소 시간을 구하여라...

문제 링크https://www.acmicpc.net/problem/31813문제양의 정수 x의 모든 자릿수가 같은 숫자로 이루어져 있다면, 그런 x를 RUN 수라고 한다. 예를 들어, 4, 111, 888, 888은 RUN 수이지만, 27, 334, 100,000은 아니다. N자리 수 K가 주어지면, K를 최대 (N+1)개의 RUN 수의 합으로 표현하라. 이는 항상 가능함을 증명할 수 있다.입력첫 번째 줄에는 테스트 케이스의 개수 T가 주어진다.각 테스트 케이스는 두 정수 N과 K가 한 줄에 공백으로 구분되어 주어진다.출력각 테스트 케이스에 대해서,첫 번째 줄에는 더해서 K를 만들 RUN 수의 개수 M을 출력한다. (1 두 번째 줄에는 해당하는 M개의 RUN 수를 공백으로 구분해서 출력한다. 만약 답이 ..

문제 링크https://www.acmicpc.net/problem/15683 문제정수로 구성된 2차원 맵을 준다.맵의 오브젝트는 다음과 같다.0: 빈 칸1~5: cctv 종류6: 벽 cctv의 종류별 감시 유형은 다음과 같다. cctv는 각 방향에 대하여 벽을 만나거나 맵의 끝에 다다르기 전까지 일직선으로 감시할 수 있다.cctv의 감시망은 벽(6)을 뚫지 못한다.또한 cctv는 90도씩 회전할 수 있다.cctv의 최대 개수는 8개다.자세한 설명은 링크를 보는 게 좋다. 예시도 친절하게 제시한다. cctv가 맵에서 감시하지 못하는 부분을 사각지대라고 하는데, cctv를 적절히 회전하여 최소 사각지대의 개수를 찾아 출력하는 문제다.  설계어차피 cctv의 최대 개수는 8개이고, 회전 각도는 90도씩 4번이..

문제 링크https://www.acmicpc.net/problem/31835  문제T | F | T & F | T & F위 식과 같이 값은 T와 F, 연산자는 |과 &로만 구성된 수식이 주어진다. | 연산은 양쪽에 있는 두 피연산자 중 하나 이상이 T이면 결괏값이 T이고, 그렇지 않으면 F이다. & 연산은 양쪽에 있는 두 피연산자가 모두 T이면 결괏값이 T이고, 그렇지 않으면 F이다. | 연산과 & 연산의 우선순위는 같고, 왼쪽부터 오른쪽으로 차례로 계산한다고 가정한다.여러분은 연산자와 값을 적절히 바꾸어 원하는 계산 결과가 나오도록 해야 한다. 이때, 연산자와 값을 바꾸는 횟수를 최소화해야 한다. 식과 원하는 계산 결과가 주어졌을 때, 원하는 계산 결과가 나오도록 연산자와 값을 고치는 최소 횟수를 구하..

문제 링크https://www.acmicpc.net/problem/31937 N대의 컴퓨터가 있다.보안 시스템을 통해, K개의 컴퓨터가 감염되었고, 이는 하나의 숙주 컴퓨터로부터 감염된 것을 확인했다.또한 보안 시스템을 통해, 숙주 컴퓨터가 감염된 시점으로부터의 컴퓨터 간 전송 기록을 확보했다."t a b" 는 t분에 a번 컴퓨터가 b번 컴퓨터로 데이터를 전송했다는 것을 의미한다.이러한 전송 기록을 통해 숙주 컴퓨터의 번호를 알아내는 문제였다. 첫째 줄: N개의 컴퓨터가 있고, M개의 전송 기록, K개의 감염된 컴퓨터가 있다.둘째 줄: 감염된 컴퓨터의 번호 (k개)셋째 줄~: M개의 전송 기록 (t a b)입력 예시5 4 33 4 54 4 53 3 42 2 31 1 2 출력 예시3 설계main() 함수는..

문제 링크 https://www.acmicpc.net/problem/2206 2206번: 벽 부수고 이동하기 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로 www.acmicpc.net 문제 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로로 이동하려 한다. 최단경로는 맵에서 가장 적은 개수의 칸을 지나는 경로를 말하는데, 이때 시작하는 칸과 끝나는 칸도 포함해서 센다. 만약에 이동하는..

문제 링크https://www.acmicpc.net/problem/25947 25947번: 선물할인입력은 표준입력을 사용한다. 첫 번째 줄에 선물의 개수를 나타내는 양의 정수 $n$ ($1 ≤ n ≤ 100\,000$), 예산을 나타내는 양의 정수 $b$ ($1 ≤ b ≤ 10^9$), 반값 할인을 받을 수 있는 최대 선물의 수를www.acmicpc.net 문제매장에서 선물을 최대한 많이 사려고 한다.메장에는 n개의 선물이 있고, 각 선물의 가격이 주어진다.이 중 a개의 선물을 반값으로 할인하여 구매할 수 있다. (한 선물을 두번 이상 반값 할인하여 구매하는 건 안됨)그리고 내 예산은 b원이다.할인을 적용했을 때 내 예산으로 구매할 수 있는 물건의 최대 개수는? 입력 양식n b agift1 gift2 ...