넘치게 채우기

https://www.acmicpc.net/problem/31455BOJ - 쿠키 자르기문제 유형: 재귀, 분할 정복문제 난이도: Silver I시간 제한: 1초메모리 제한: 512MB 문제Albert는 2K×2K 크기의 쿠키를 구워 각 칸에 0-9 사이의 숫자를 적어두었다 - 이 문제에서 편의상 r 행 c열에 적힌 숫자는 A[r,c]로 나타내자 (0≤A[r,c]≤9).예를 들어 아래 그림은 K=2 이고 A=[[1,2,3,4],[2,3,4,5],[3,4,5,6],[0,9,8,7]] 인 쿠키의 모습을 보여준다.구워진 쿠키를 감상하던 Bob은 Albert에게 아래와 같은 놀이를 제안했다.크기가 N×N인 쿠키를 N/2×N/2 크기로 4등분 하여 그 중 한 조각을 둘이 나눠 먹는다.우선 아래 그림의 좌측과 같이..

https://www.acmicpc.net/problem/1106BOJ - 호텔문제 유형: 다이나믹 프로그래밍, 배낭 문제문제 난이도: Gold IV시간 제한: 2초메모리 제한: 128MB 문제세계적인 호텔인 형택 호텔의 사장인 김형택은 이번에 수입을 조금 늘리기 위해서 홍보를 하려고 한다.형택이가 홍보를 할 수 있는 도시가 주어지고, 각 도시별로 홍보하는데 드는 비용과, 그 때 몇 명의 호텔 고객이 늘어나는지에 대한 정보가 있다.예를 들어, “어떤 도시에서 9원을 들여서 홍보하면 3명의 고객이 늘어난다.”와 같은 정보이다. 이때, 이러한 정보에 나타난 돈에 정수배 만큼을 투자할 수 있다. 즉, 9원을 들여서 3명의 고객, 18원을 들여서 6명의 고객, 27원을 들여서 9명의 고객을 늘어나게 할 수 있지..

https://www.acmicpc.net/problem/1513BOJ - 경로 찾기문제 유형: 다이나믹 프로그래밍문제 난이도: Gold II시간 제한: 2초메모리 제한: 128MB 문제세준이는 크기가 N*M인 직사각형 도시에 살고 있다. 또, 세준이의 집은 (1, 1)에 있고, 학원은 (N, M)에 있고, 오락실이 C개 있다.세준이의 현재 위치가 (r, c) 일 때, (r+1, c) 또는 (r, c+1)로만 이동할 수 있다. 오락실을 방문할 때는 규칙이 하나 있는데, 오락실 번호가 증가하는 순서대로 가야한다는 것이다. 2번 오락실을 먼저 가고, 그 후에 1번 오락실을 가면 안 되고, 2번 오락실을 가려면, 그 전에 아무 오락실도 가지 않거나, 1번 오락실을 방문했을 때만 가능하다.세준이는 오락실을 K번..

https://www.acmicpc.net/problem/4929BOJ - 수열 걷기문제 유형: 그리디, 구간합, 투포인터, 구현문제 난이도: Silver I시간 제한: 1초메모리 제한: 128MB 문제길이가 유한하고, 오름차순 순서로 되어있는 두 수열이 주어진다. 두 수열에 공통으로 들어있는 원소는 교차점으로 생각할 수 있다.아래는 두 수열과 교차점은 굵게 나타낸 것이다.수열 1 = 3 5 7 9 20 25 30 40 55 56 57 60 62수열 2 = 1 4 7 11 14 25 44 47 55 57 100이 두 수열은 다음과 같이 걸을 수 있다.두 수열중 하나의 첫 번째 원소에서 걷기를 시작한다. 걷는 것은 앞으로만 걸을 수 있다.교차점에 도착했을 때는, 현재 수열에서 계속 걸을지, 다른 수열로 갈..

https://www.acmicpc.net/problem/29717BOJ - 슬라임 잡고 레벨 업문제 유형: 수학, 이분 탐색, 매개 변수 탐색문제 난이도: Silver II시간 제한: 1초메모리 제한: 1024MB 문제오늘은 많은 사람이 기대하던 《실브 스토리》게임이 출시되는 날이다!《실브 스토리》는 MMORPG 장르 게임으로, 몬스터를 잡아 경험치를 모으고 레벨 업을 할 수 있으며, 레벨 업에 필요한 경험치를 넘을 때마다 그에 필요한 경험치만 소진하고 남은 경험치를 그대로 보유한다. 하지만 일반 게임들과 다르게 특이한 점이 두 가지 있다.첫 번째는 게임에 존재하는 몬스터가 슬라임뿐이라는 것이다. 슬라임을 처치했을 때 주는 경험치 또한 특이한데, 유저가 지금까지 처치한 슬라임 수를 x라 할 때, 새로운..

https://www.acmicpc.net/problem/17253BOJ - 삼삼한 수 2문제 유형: 수학문제 난이도: Silver III시간 제한: 1초메모리 제한: 256MB 문제준하는 3의 거듭제곱인 수만 사용하여 만들 수 있는 수를 보면 삼삼한 느낌을 받는다.이 느낌을 정확히 설명하자면, 3의 거듭제곱인 수들을 겹치지 않고 한번씩만 더해서 어떤 수 x를 만들 수 있다면 그 수는 삼삼하다고 한다. 삼삼한 수는 3의 거듭제곱인 수가 반드시 하나 이상 포함되어야 한다.예를 들어, 10^9는 3^0+3^3+3^4로 나타낼 수 있으므로 삼삼한 수이다. 하지만 7과 18은 삼삼하지 않다.준하는 삼삼한 수가 얼마나 더 있는 지 알아보려고 한다. 입력첫째 줄에 9,223,372,036,854,775,807보다 ..

https://www.acmicpc.net/problem/14890BOJ - 경사로문제 유형: 구현문제 난이도: Gold III시간 제한: 2초메모리 제한: 512MB 문제크기가 N×N인 지도가 있다. 지도의 각 칸에는 그 곳의 높이가 적혀져 있다.오늘은 이 지도에서 지나갈 수 있는 길이 몇 개 있는지 알아보려고 한다. 길이란 한 행 또는 한 열 전부를 나타내며, 한쪽 끝에서 다른쪽 끝까지 지나가는 것이다.다음과 같은 N=6인 경우 지도를 살펴보자. 이때, 길은 총 2N개가 있으며, 아래와 같다. 길을 지나갈 수 있으려면 길에 속한 모든 칸의 높이가 모두 같아야 한다. 또는, 경사로를 놓아서 지나갈 수 있는 길을 만들 수 있다. 경사로는 높이가 항상 1이며, 길이는 L이다. 또, 개수는 매우 많아 부족할..

https://www.acmicpc.net/problem/1409BOJ - 점 칠하기문제 유형: dfs, 이분 그래프, 이분 매칭, 브루트 포스문제 난이도: Gold I시간 제한: 2초메모리 제한: 128MB 문제다솜이는 친구가 없는 왕따이기 때문에, 혼자 노는 놀이는 거의 다 완벽하게 익혔다. 하지만, 다솜이가 정복하지 못한 놀이가 하나 있었다. 바로 어떤 원 위에 점을 색칠하면서 노는 것이다.다솜이는 원 위에 2N개의 점을 찍어놓고, 각각의 점을 빨간색과 파란색으로 칠하려고 한다. 다솜이는 그냥 칠하는 것은 왕따의 본분에 맞지 않다고 생각했기 때문에, 규칙을 정했다.다솜이가 정한 규칙은 빨간색으로 칠한 점들을 어떤 각도로 일정하게 돌리면 파란색점과 겹쳐진다는 것이다.예를 들어, 어떤 원에서 0, 10..

https://www.acmicpc.net/problem/31674BOJ - 특별한 기술력문제 유형: 애드 혹, 그리디, 수학문제 난이도: Silver II시간 제한: 1초메모리 제한: 1024MB 문제NLCS의 기술력은 세계 제일이다.기술력이 뛰어난 NLCS Jeju는 키가 커지고 싶은 학생들을 위해 키가 커지는 도구 "요술 망치"를 개발하였다.키가 커지고 싶어 요술 망치의 임상실험에 참여한 N명의 학생들에게 요술 망치를 사용하는 실험을 진행하게 되었다. 어떤 학생에게 요술 망치를 사용하면 그 학생의 키만큼 다른 모든 학생의 키가 커진다. 하지만 요술 망치는 아직 프로토타입 단계라 한 학생에게 최대 한 번밖에 사용할 수 없다.NLCS Jeju는 요술 망치의 대단함을 강조하기 위해 요술 망치를 사용한 후..

https://www.acmicpc.net/problem/31498BOJ - 장난을 잘 치는 토카 양문제 유형: 이진 탐색, 매개 변수 탐색, 많은 조건 분기문제 난이도: Gold V시간 제한: 1초메모리 제한: 1024MB 문제장난기 많은 도발꾼 토카는 오늘도 친구인 돌돌이를 도발하고 말았다. 돌돌이는 도발에 넘어갔고, 죽일 듯이 토카를 쫓아오기 시작했다! 토카는 돌돌이로부터 무사히 도망치기 위해 집까지 돌아가 문을 잠가야 한다. 토카는 집과 A만큼 떨어진 곳에 있고, 돌돌이는 토카와 같은 방향으로 집과 A+C만큼 떨어져 있다. 집, 토카, 돌돌이는 직선상에 놓여있다.토카는 집을 향해 사력을 다하여 이동하고, 한 번 이동할 때 B만큼 이동한다. 하지만 토카는 체력이 좋지 않기 때문에, 한 번 이동하고 ..