백준 2885 - 초콜릿 식사 시간 제한 1초, 메모리 제한 128MB # 조건 학교 근처 편의점에 새 초콜릿이 들어왔다. 이 초콜릿은 막대 모양이고, 각 막대는 정사각형 N개로 이루어져 있다. 초콜릿의 크기(정사각형의 개수)는 항상 2의 제곱 형태이다. 즉, 1, 2, 4, 8, 16, ...개의 정사각형으로 이루어져 있다. 상근이는 점심식사로 초콜릿을 먹는다. 이때, 적어도 K개 정사각형을 먹어야 남은 수업을 졸지 않고 버틸 수 있다. 상근이의 친구 선영이도 초콜릿을 좋아한다. 선영이는 초콜릿은 돈을 주고 사기 아깝다고 생각하기 때문에, 상근이가 주는 초콜릿만 먹는다. 상근이는 막대 초콜릿를 하나 산 다음에, 정확하게 K개 정사각형이 되도록 초콜릿을 쪼갠다. K개는 자신이 먹고 남는 것은 선영이에게 ..

백준 10844 - 쉬운 계단 수 시간 제한 1초, 메모리 제한 256MB # 조건 45656이란 수를 보자. 이 수는 인접한 모든 자리의 차이가 1이다. 이런 수를 계단 수라고 한다. N이 주어질 때, 길이가 N인 계단 수가 총 몇 개 있는지 구해보자. 0으로 시작하는 수는 계단수가 아니다. 입력 첫째 줄에 N이 주어진다. N은 1보다 크거나 같고, 100보다 작거나 같은 자연수이다. 출력 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. # 접근 방법 2차원 리스트를 활용한 DP로 풀어주었다. 문제의 핵심은 제일 뒤의 숫자가 어떤 숫자인지에 따라 DP의 값을 누적해나가는 것이다. 1자리 수의 경우 0을 제외한 1~9에 1을 기입해준다. 2자리 수의 경우 뒷 자리가 0인 경우 10..

백준 2665 - 미로만들기시간 제한 1초, 메모리 제한 128MB# 조건n×n 바둑판 모양으로 총 n2개의 방이 있다.일부분은 검은 방이고 나머지는 모두 흰 방이다.검은 방은 사면이 벽으로 싸여 있어 들어갈 수 없다.서로 붙어 있는 두 개의 흰 방 사이에는 문이 있어서 지나다닐 수 있다.윗줄 맨 왼쪽 방은 시작방으로서 항상 흰 방이고, 아랫줄 맨 오른쪽 방은 끝방으로서 역시 흰 방이다.시작방에서 출발하여 길을 찾아서 끝방으로 가는 것이 목적인데, 아래 그림의 경우에는 시작방에서 끝 방으로 갈 수가 없다.부득이 검은 방 몇 개를 흰 방으로 바꾸어야 하는데 되도록 적은 수의 방의 색을 바꾸고 싶다.아래 그림은 n=8인 경우의 한 예이다.위 그림에서는 두 개의 검은 방(예를 들어 (4,4)의 방과 (7,8)..

백준 5883 - 아이폰 9S 시간 제한 1초, 메모리 제한 128MB # 조건 오늘은 애플의 아이폰 9S가 출시되는 날이다. N(1 ≤ N ≤ 1000)명의 사람들은 새 아이폰을 누구보다 먼저 구매하기 위해서 애플 스토어 앞에 한 줄로 서있다. 아이폰 9S는 구매자가 용량을 마음대로 정할 수 있다. 즉, 지금까지 아이폰은 16/32/64GB와 같이 용량의 크기가 미리 정해져 있었다. 하지만, 9S는 자신이 원하는 용량의 크기 B(i)를 점원에게 말하면, 정확하게 그 용량을 가진 아이폰 9S를 그 자리에서 만들어 구매하는 방식이다. 애플 스토어의 점원 상근이는 같은 용량을 원하는 사람들이 연속되어 있으면, 더 보기 좋을 것이라고 생각한다. 따라서, 특정 사람을 고르고, 그 사람이 원하는 용량을 원하는 사..

백준 1939 - 중량제한 시간 제한 1초, 메모리 제한 128MB # 조건 N(2 ≤ N ≤ 10,000)개의 섬으로 이루어진 나라가 있다. 이들 중 몇 개의 섬 사이에는 다리가 설치되어 있어서 차들이 다닐 수 있다. 영식 중공업에서는 두 개의 섬에 공장을 세워 두고 물품을 생산하는 일을 하고 있다. 물품을 생산하다 보면 공장에서 다른 공장으로 생산 중이던 물품을 수송해야 할 일이 생기곤 한다. 그런데 각각의 다리마다 중량제한이 있기 때문에 무턱대고 물품을 옮길 순 없다. 만약 중량제한을 초과하는 양의 물품이 다리를 지나게 되면 다리가 무너지게 된다. 한 번의 이동에서 옮길 수 있는 물품들의 중량의 최댓값을 구하는 프로그램을 작성하시오. 입력 첫째 줄에 N, M(1 ≤ M ≤ 100,000)이 주어진다..

백준 1890 - 점프 시간 제한 1초, 메모리 제한 128MB # 조건 N×N 게임판에 수가 적혀져 있다. 이 게임의 목표는 가장 왼쪽 위 칸에서 가장 오른쪽 아래 칸으로 규칙에 맞게 점프를 해서 가는 것이다. 각 칸에 적혀있는 수는 현재 칸에서 갈 수 있는 거리를 의미한다. 반드시 오른쪽이나 아래쪽으로만 이동해야 한다. 0은 더 이상 진행을 막는 종착점이며, 항상 현재 칸에 적혀있는 수만큼 오른쪽이나 아래로 가야 한다. 한 번 점프를 할 때, 방향을 바꾸면 안 된다. 즉, 한 칸에서 오른쪽으로 점프를 하거나, 아래로 점프를 하는 두 경우만 존재한다. 가장 왼쪽 위 칸에서 가장 오른쪽 아래 칸으로 규칙에 맞게 이동할 수 있는 경로의 개수를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 게임 판의 크기 ..

백준 19949 - 영재의 시험 시간 제한 1초, 메모리 제한 512MB # 조건 컴퓨터공학과 학생인 영재는 이번 학기에 알고리즘 수업을 수강한다. 평소에 자신의 실력을 맹신한 영재는 시험 전날까지 공부를 하지 않았다. 당연하게도 문제를 하나도 풀지 못하였지만 다행히도 문제가 5지 선다의 객관식 10문제였다. 찍기에도 자신 있던 영재는 3개의 연속된 문제의 답은 같지 않게 한다는 자신의 비법을 이용하여 모든 문제를 찍었다. 이때 영재의 점수가 5점 이상일 경우의 수를 구하여라. 문제의 점수는 1문제당 1점씩이다. 입력 시험의 정답이 첫 줄에 주어진다. 출력 영재의 점수가 5점 이상일 경우의 수를 출력하여라. # 접근 방법 product - 중복순열을 이용하여 모든 조건을 탐색해주어도 되지만 시간이 상당히..

백준 17135 - 캐슬 디펜스 시간 제한 1초, 메모리 제한 512MB # 조건 캐슬 디펜스는 성을 향해 몰려오는 적을 잡는 턴 방식의 게임이다. 게임이 진행되는 곳은 크기가 N×M인 격자판으로 나타낼 수 있다. 격자판은 1×1 크기의 칸으로 나누어져 있고, 각 칸에 포함된 적의 수는 최대 하나이다. 격자판의 N번행의 바로 아래(N+1번 행)의 모든 칸에는 성이 있다. 성을 적에게서 지키기 위해 궁수 3명을 배치하려고 한다. 궁수는 성이 있는 칸에 배치할 수 있고, 하나의 칸에는 최대 1명의 궁수만 있을 수 있다. 각각의 턴마다 궁수는 적 하나를 공격할 수 있고, 모든 궁수는 동시에 공격한다. 궁수가 공격하는 적은 거리가 D이하인 적 중에서 가장 가까운 적이고, 그러한 적이 여럿일 경우에는 가장 왼쪽에..

백준 20924 - 트리의 기둥과 가지 시간 제한 2.5초(추가 시간 x), 메모리 제한 1024MB # 조건 시청 공무원 마이크로는 과장으로부터 시에 있는 나무와 기둥의 길이와 가장 긴 가지의 길이를 파악하라는 업무 지시를 받았다. 마이크로는 ICPC Sinchon Winter Algorithm Camp에서 배운 트리 자료 구조를 이용하면 이 작업을 좀 더 수월하게 할 수 있으리라 판단했다. 마이크로는 트리의 기둥과 가지를 분류하기 위해 기가 노드를 추가로 정의하였다. 기가 노드는 루트 노드에서 순회를 시작했을 때, 처음으로 자식 노드가 $2$개 이상인 노드다. 기둥-가지를 줄여 기가 노드라 이름 붙였다. 위 그림에서 기가 노드는 $4$번 노드다. 단, 리프 노드가 1개인 경우 리프 노드가 동시에 기가..