본문 바로가기

문제 노트

 (157)
영훈이의 색칠공부( BOJ 14578 ) 문제 : https://www.acmicpc.net/problem/14578 14578번: 영훈이의 색칠공부 영훈이가 색칠 할 수 있는 모든 경우의 수를 1,000,000,007로 나눈 나머지를 출력하시오. www.acmicpc.net 문제 파악하기 N*N 격자판에 빨간색과 파란색을 색칠하는 경우의 수를 구하는 문제입니다. 당연히 아무 칸에 색칠할 수 있는 건 아니고, 모든 행과 열에 빨간색과 파란색을 하나씩 색칠해야 합니다. 결국 N개의 빨간색과 파란색을 행과 열이 중복되지 않게 배치할 수 있는 방법의 수를 구하는 문제입니다. 2차원 배열을 하나씩 채워 나가기에는 105라는 숫자가 너무도 크기에 다른 방법을 생각해보아야 합니다. 그럼 어떤 방법이 있을까요? 우선은 문제를 분석해봅시다. 만약 3*3격자판..
용량 확보( BOJ 9327 ) 문제 : https://www.acmicpc.net/problem/9327 9327번: 용량 확보 NSA는 점점 늘어나는 러시아어와 스페인어 번역 데이터와 전화 도청 파일의 용량 때문에, 데이터 센터의 용량을 최대 1 엑사바이트로 확장하려고 한다. NSA의 예산은 넉넉한 편이 아니기 때문에, www.acmicpc.net 문제 파악하기 입력되는 e만큼 용량을 확보하기 위해 변환해야 하는 용량의 최소값을 구하는 문제입니다. 용량을 확장하면 기존 용량보다 3배 커지게 됩니다. 이를 용량을 확보하는 관점에서 보자면 확장 시 기존 용량*2 만큼 확보할 수 있습니다. 이 점에 주목하면 문제를 해결할 알고리즘을 설계할 수 있습니다. 문제 해결하기 우리는 항상 i번째 세트를 확장시키면 기존 용량*2만큼 추가 공간을 확..
사과와 바나나( BOJ 3114 ) 문제 : https://www.acmicpc.net/problem/3114 3114번: 사과와 바나나 첫 번째 예제의 경우 불도저가 오른쪽-아래, 오른쪽-아래, 아래로 이동하면 된다. 경로의 아래에 있는 사과 나무의 개수는 3+2+4=9개이고, 위에 있는 바나나 나무의 개수는 3+5=8개이다. www.acmicpc.net 문제 파악하기 2차원 배열의 값을 적절하게 위/아래로 나눠, 위에 있는 B의 합과 아래에 있는 A의 합의 최댓값을 구하는 문제입니다. 불도저는 항상 (1, 1)에서 출발하여 3가지 방향(오른쪽, 아래, 대각선 아래)으로만 움직이기 때문에 우리는 특정 위치 (x, y)에 도착하기 위해서는 적어도 (x-1, y) / (x, y-1) / (x-1, y-1)에서 이동해야 합니다. 또한, 이전 ..
절사평균( BOJ 6986 ) 문제 : https://www.acmicpc.net/problem/6986 6986번: 절사평균 첫째 줄에 절사평균(N, K)를, 둘째 줄에 보정평균(N, K)를 각각 소수점이하 셋째 자리에서 반올림하여 둘째 자리까지 출력한다. 예를 들어 결과값이 9.667인 경우 9.67로, 5인 경우 5.00으로, 5.5인 경우 www.acmicpc.net 문제 파악하기 체조경기에서 사용하는 평균 계산법인 절사평균과 보정평균을 구하는 문제입니다. 다만, 입력이 실수로 주어지기 때문에 오차가 발생하기 쉽다는 점을 간과한다면 절대 풀 수 없는 문제입니다. 절사평균과 보정평균을 구하는 방법은 간단합니다. 모든 입력값을 정렬한 다음, 양 쪽의 K개 숫자를 없애거나(절사평균) K개 숫자를 인근 숫자로 변환(보정평균)한 다음,..
낚시왕( BOJ 17143) 문제 : https://www.acmicpc.net/problem/17143 17143번: 낚시왕 낚시왕이 상어 낚시를 하는 곳은 크기가 R×C인 격자판으로 나타낼 수 있다. 격자판의 각 칸은 (r, c)로 나타낼 수 있다. r은 행, c는 열이고, (R, C)는 아래 그림에서 가장 오른쪽 아래에 있는 칸이다. www.acmicpc.net 문제 파악하기 낚시왕이 1열부터 C열까지 이동하면서 잡은 상어들의 크기를 모두 구하는 문제입니다. 낚시왕과 상어들은 일련의 단계에 맞춰 행동하며, 우리는 낚시왕과 상어들이 규칙에 맞게 움직일 수 있도록 알고리즘을 설계해야 합니다. 문제 해결하기 우선 가장 처음 단계는 낚시왕이 오른쪽으로 한칸 이동하여 해당 열에 있는 상어 중 땅과 가장 가까운 상어를 잡습니다. 이 경우..
종이 접기( BOJ 1802 ) 문제 : https://www.acmicpc.net/problem/1802 1802번: 종이 접기 첫째 줄에 테스트 케이스의 개수 T가 주어진다. T는 1000보다 작거나 같은 자연수이다. 둘째 줄부터 T개의 줄에 각각의 종이가 어떻게 접혀있는지가 주어진다. 종이의 정보는 문자열로 주어지며, 1 www.acmicpc.net 문제 파악하기 항상 종이를 절반씩 접는다고 할 때, 제시된 문자열로 종이를 접을 수 있는지 확인하는 문제입니다. 종이를 절반씩 접게 되면, 항상 접은 부분을 중심으로 양쪽에는 반대로 접힌 흔적이 남게 됩니다. 이를 활용하면 문제를 해결할 수 있습니다. 문제 해결하기 종이를 접어 생기는 흔적은 항상 중앙에 생기게 됩니다. 그리고 생긴 흔적을 중심으로 항상 반대로 접히게 됩니다. 예를 들..
7-세그먼트 디스플레이( BOJ 18118 ) 문제 : https://www.acmicpc.net/problem/18118 18118번: 7-세그먼트 디스플레이 각 테스트 케이스마다 n개의 7-세그먼트 디스플레이에 표현할 수 있는 가장 큰 m의 배수를 한 줄에 하나씩 출력한다. 가능한 가장 큰 값이 0일 경우, "0"(따옴표 제외)을 출력한다. www.acmicpc.net 문제 파악하기 N개의 디스플레이에 숫자를 표시하여 만들 수 있는 가장 큰 M의 배수를 구하는 문제입니다. 주의할 점은 디스플레이에는 0부터 9까지 숫자와 11을 넣을 수 있다는 점입니다. 만들 수 있는 숫자는 대략 가늠해봐도 1억개 그 이상이라 단순히 반복문을 사용해서는 찾을 수 없습니다. 그렇다면 어떤 방법이 있을까요? 이런 경우, 효율적인 탐색 방법이 필요하며 그 때 생각할 수..
K번째 수( BOJ 1300 ) 문제 : https://www.acmicpc.net/problem/1300 1300번: K번째 수 세준이는 크기가 N×N인 배열 A를 만들었다. 배열에 들어있는 수 A[i][j] = i×j 이다. 이 수를 일차원 배열 B에 넣으면 B의 크기는 N×N이 된다. B를 오름차순 정렬했을 때, B[k]를 구해보자. 배열 A와 B www.acmicpc.net 문제 파악하기 2차원 배열 A[i][j]의 값을 정렬하여 1차원 배열 B[i]로 변환한 다음, K번째 숫자를 출력하는 문제입니다. 가장 쉬운 방법이라면 1차원 배열 B를 만든 다음, 2차원 배열 A에 있는 모든 값을 저장한 후 정렬하여 B[K]를 출력하면 됩니다. 하지만 이 문제는 배열의 크기가 최대 100,000*100,000 = 10,000,000,000..

티스토리툴바