이 험난한 세상에서어어~

문제 설명 테트로미노 5개를 주어진 2차원 배열에 두었을 때 각 칸의 합의 최댓값을 구하는 문제이다. 이때 테트로미노는 회전하거나 대칭시켜도 된다. https://www.acmicpc.net/problem/14500 14500번: 테트로미노 폴리오미노란 크기가 1×1인 정사각형을 여러 개 이어서 붙인 도형이며, 다음과 같은 조건을 만족해야 한다. 정사각형은 서로 겹치면 안 된다. 도형은 모두 연결되어 있어야 한다. 정사각형의 변 www.acmicpc.net 문제 풀이 문제를 처음 봤을 때는 테트로미노로 만들 수 있는 모든 문양을 2차원 배열로 만든 다음에 주어진 지도에 대입시키려고 했다. 그러나 파란색과 노란색은 경우의 수가 적지만 주황색부터는 경우의 수가 너무 많아져서 분명 다른 풀이가 있을 거라는 생..

문제 설명 크기가 3x3인 배열이 있다. 이때 행의 개수가 열의 개수보다 크거나 같으면 행을 기준으로 정렬하고 반대이면 열을 기준으로 정렬을 한다. 이때 정렬의 기준은 각 수가 얼마나 많이 등장하는지, 만일 같다면 각 수의 크기이다. 예를 들어서 [3, 1, 1]이 있다면 1은 총 2번 나왔고 3은 총 1번 나왔으니 (1, 2), (3, 1) 이렇게 정렬이 되는 것이다. 이때 정렬은 수를 먼저 넣어준다. 100초 안쪽으로 위의 정렬을 해줄 건데 arr[r][c]에서 k가 나올 때 얼마나 많은 시간이 걸리는지 구하는 문제이다. 만일 100초를 넘어갔는데 결과를 내지 못한다면 -1을 출력한다. 단, 배열의 수가 0이라면 정렬 대상이 아니다. 사실 이 문제는 힌트를 보면 빠르게 이해할 수 있다. 힌트에서 나왔..

문제 설명 사과를 먹으면 몸의 길이가 늘어나는 뱀이 있다. 뱀이 이리저리 돌아다니다가 자기 자신 혹은 벽과 부딪히면 게임이 끝이 난다. 이때 게임이 몇 초에 끝나는지 구하는 문제이다. 조건 1. 뱀은 머리를 늘려 다음 칸에 머리를 위치시킨다. 2. 만일 다음 칸이 벽이거나 칸에 자기 자신이 있을 경우 게임이 중료된다. 3. 만일 2번 조건이 아니고 다음 칸에 사과가 있을 경우 사과를 먹는다. 사과가 없다면 꼬리를 한 칸 줄이는데 이경우 몸 길이를 유지한다. https://www.acmicpc.net/problem/3190 3190번: 뱀 'Dummy' 라는 도스게임이 있다. 이 게임에는 뱀이 나와서 기어다니는데, 사과를 먹으면 뱀 길이가 늘어난다. 뱀이 이리저리 기어다니다가 벽 또는 자기자신의 몸과 부딪..

문제 설명 여러 지방에 예산을 분배해야 한다. 하지만, 국가 예산의 총액은 이미 정해져 있어 총액 내에서만 분배가 가능하다. 만일 지방에서 요구한 예산이 기준보다 작다면 요구한 예산을 분배하고 크다면 기준을 분배한다. 이때 기준의 최댓값을 구하는 문제이다. https://www.acmicpc.net/problem/2512 2512번: 예산 첫째 줄에는 지방의 수를 의미하는 정수 N이 주어진다. N은 3 이상 10,000 이하이다. 다음 줄에는 각 지방의 예산요청을 표현하는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 값들은 모두 1 이상 www.acmicpc.net 참고! 예산 기준이 정해지면 (예산 기준 * 지방의 수)가 총 예산 안에 들어갈 필요는 없다. 어차피 예산 기준보다 작은 예산들은 각 지..

문제 설명 K개의 랜선이 있을 때 적당하게 잘라서 N개의 랜선으로 만들고 싶다. 이때 자르는 길이의 최댓값을 구하는 문제이다. 이때 자른 랜선의 길이가 N개보다 커도 된다. 즉, K개의 랜선을 자를 때 만들 수 있는 랜선이 N개 이상이 되는 최댓값을 구하면 된다. https://www.acmicpc.net/problem/1654 1654번: 랜선 자르기 첫째 줄에는 오영식이 이미 가지고 있는 랜선의 개수 K, 그리고 필요한 랜선의 개수 N이 입력된다. K는 1이상 10,000이하의 정수이고, N은 1이상 1,000,000이하의 정수이다. 그리고 항상 K ≦ N 이다. 그 www.acmicpc.net 다만, 여기서 조심할 점이 굳이 K개의 랜선을 모두 자를 필요는 없다는 거다. 문제 풀이 첫 번째 접근 랜..

문제 설명 상근이는 나무를 자르려고 한다. 이때 상근이는 환경에 관심이 많아 필요한 만큼의 나무만 들고가려고 한다. 이때 가질 수 있는 톱의 최대 높이를 구하는 문제이다. https://www.acmicpc.net/problem/2805 2805번: 나무 자르기 첫째 줄에 나무의 수 N과 상근이가 집으로 가져가려고 하는 나무의 길이 M이 주어진다. (1 ≤ N ≤ 1,000,000, 1 ≤ M ≤ 2,000,000,000) 둘째 줄에는 나무의 높이가 주어진다. 나무의 높이의 합은 항상 M보 www.acmicpc.net 간단히 설명하자면 상근이가 나무를 자르는데, 잘린 나무의 값과 주어진 M의 값의 오차가(무조건 양수) 최소가 되게 하는 높이를 구하는 문제이다. 문제 풀이 이진탐색 자를 높이를 이진탐색으로..