넘치게 채우기

https://www.acmicpc.net/problem/14916BOJ - 거스름돈문제 유형: 수학, 다이나믹 프로그래밍, 브루트 포스, 그리디, 조건 분기문제 난이도: Silver V시간 제한: 2초메모리 제한: 512MB 문제춘향이는 편의점 카운터에서 일한다.손님이 2원짜리와 5원짜리로만 거스름돈을 달라고 한다. 2원짜리 동전과 5원짜리 동전은 무한정 많이 가지고 있다. 동전의 개수가 최소가 되도록 거슬러 주어야 한다. 거스름돈이 n인 경우, 최소 동전의 개수가 몇 개인지 알려주는 프로그램을 작성하시오.예를 들어, 거스름돈이 15원이면 5원짜리 3개를, 거스름돈이 14원이면 5원짜리 2개와 2원짜리 2개로 총 4개를, 거스름돈이 13원이면 5원짜리 1개와 2원짜리 4개로 총 5개를 주어야 동전의 개..

https://www.acmicpc.net/problem/18231BOJ - 파괴된 도시문제 유형: 해 구성하기, 그래프 이론문제 난이도: Gold V시간 제한: 2초메모리 제한: 512MB 문제저명한 역사학자 지수는 오래된 지도 한 장을 주웠다. 이 지도는 N개의 도시와 M개의 도로로 이루어져 있으며, 각 도시는 1부터 N까지 하나씩 번호가 매겨져있다. 지도에는 불에 탄 모습의 K개의 도시가 있었는데, 지수는 이 지도가 전쟁 당시 파괴된 도시를 표시한 지도임을 알아차렸다. 연구한 바에 의하면, 어떤 도시에 그 당시 사용했던 폭탄을 떨어뜨리면 이 도시를 포함하여 인접한 도시들은 전부 파괴된다고 한다.지수는 이 사실을 토대로 당시 폭탄이 떨어진 지점들을 알아내기 위해 우리를 초대했다. 우리는 폭탄이 떨어진..

https://www.acmicpc.net/problem/1451BOJ - 직사각형으로 나누기문제 유형: 누적합, 브루트 포스, 많은 조건 분기문제 난이도: Gold IV시간 제한: 2초메모리 제한: 128MB 문제세준이는 N*M크기로 직사각형에 수를 N*M개 써놓았다.세준이는 이 직사각형을 겹치지 않는 3개의 작은 직사각형으로 나누려고 한다. 각각의 칸은 단 하나의 작은 직사각형에 포함되어야 하고, 각각의 작은 직사각형은 적어도 하나의 숫자를 포함해야 한다.어떤 작은 직사각형의 합은 그 속에 있는 수의 합이다. 입력으로 주어진 직사각형을 3개의 작은 직사각형으로 나누었을 때, 각각의 작은 직사각형의 합의 곱을 최대로 하는 프로그램을 작성하시오. 입력첫째 줄에 직사각형의 세로 크기 N과 가로 크기 M이 ..

https://www.acmicpc.net/problem/2313BOJ - 보석 구매하기문제 유형: 다이나믹 프로그래밍, 구간 합문제 난이도: Gold V시간 제한: 2초메모리 제한: 128MB 문제보석 가게에 여러 가지의 보석이 진열되어 있다. 각각의 보석은 정수로 표현되는 가치가 있다. 때로는 저주받은 보석이 있기 때문에 가치가 음수가 될 수도 있다.보석들은 총 n개의 줄에 나열되어 있다. 이제 당신은 각각의 줄에서 몇 개의 보석을 구매하려 한다. 이때, 각 줄에서 보석을 구매할 때 연속적인 보석들을 구매해야 한다. 즉, 어느 한 줄에서 1, 2번 보석을 구매할 수도 있고, 2, 3번 보석을 구매할 수도 있지만, 1, 3번 보석을 구매할 수는 없다.구매하는 보석의 가치의 총 합이 최대가 되도록 보석을..

https://www.acmicpc.net/problem/2718BOJ - 타일 채우기문제 유형: 다이나믹 프로그래밍문제 난이도: Gold I시간 제한: 1초메모리 제한: 128MB 문제4*N 크기의 타일을 2*1, 1*2 크기의 도미노로 완전히 채우려고 한다. 예를 들어 4*2 타일을 채우는 방법은 다음과 같이 5가지가 있다.N이 주어졌을 때, 타일을 채우는 방법의 개수를 출력하는 프로그램을 작성하시오. 입력첫째 줄에 테스트 케이스의 개수 T가 주어진다. T는 1,000보다 작거나 같은 자연수이다. 각 테스트 케이스는 정수 하나로 이루어져 있다. 이 정수는 문제에서 설명한 타일의 너비 N이다. N은 자연수이다.N은 타일을 채우는 경우의 수가 2,147,483,647 이하이도록 주어진다. 출력각 테스트 ..

https://www.acmicpc.net/problem/1388BOJ - 바닥 장식문제 유형: 구현, dfs/bfs문제 난이도: Silver IV시간 제한: 2초메모리 제한: 128MB 문제형택이는 건축가이다. 지금 막 형택이는 형택이의 남자 친구 기훈이의 집을 막 완성시켰다. 형택이는 기훈이 방의 바닥 장식을 디자인했고, 이제 몇 개의 나무 판자가 필요한지 궁금해졌다. 나무 판자는 크기 1의 너비를 가졌고, 양수의 길이를 가지고 있다. 기훈이 방은 직사각형 모양이고, 방 안에는 벽과 평행한 모양의 정사각형으로 나누어져 있다.이제 ‘-’와 ‘|’로 이루어진 바닥 장식 모양이 주어진다. 만약 두 개의 ‘-’가 인접해 있고, 같은 행에 있다면, 두 개는 같은 나무 판자이고, 두 개의 ‘|’가 인접해 있고,..

https://www.acmicpc.net/problem/12755BOJ - 수면 장애문제 유형: 수학, 브루트 포스, 구현문제 난이도: Silver IV시간 제한: 1초메모리 제한: 128MB 문제수면 장애를 가진 강민이는 잠이 오지 않아 적잖은 고통을 느끼고 있다. 강민이는 잠이 오지 않을 때마다 속으로 양을 세고 있었는데, 오늘따라 백만 마리까지 세었는데도 잠이 오지 않았다.한계를 느낀 강민이는 새로운 방법으로 수를 세기로 했다.1부터 숫자를 쭉 이어 붙이면 다음과 같은 숫자열이 생성된다.12345678910111213...강민이는 이 숫자열을 한 숫자씩 떼어서 읽기 시작했다. 수면에 성공한 강민이는 다음날 일어나자마자 "N번째 숫자까지 읽었어!" 라고 기분 좋게 외쳤다.과연 N번째 숫자는 무엇일까..

https://www.acmicpc.net/problem/13021BOJ - 13021 - 공 색칠하기문제 유형: 애드 혹, 수학, 조합론문제 난이도: Silver I시간 제한: 1초메모리 제한: 512MB 문제공 N개가 한 줄로 놓여져 있다. 공은 검정색 또는 흰색으로 칠할 수 있으며, 처음에 모든 공의 색은 흰색이다. 공은 가장 왼쪽이 1번이고, 순서대로 번호가 매겨져 있다.오늘은 공을 칠해보려고 한다. 공은 기계를 이용해서 칠할 수 있는데, 기계는 두 정수 L과 R을 입력으로 받는다. 기계는 L번째 공부터 R번째 공까지를 흰색이나 검정색으로 모두 칠한다.기계를 총 M번 사용했고, 이때 입력한 L과 R을 모두 알고있다. 하지만, 어떤 색으로 칠했는지는 까먹고 말았다. 기계를 모두 M번 사용했을 때, ..

https://www.acmicpc.net/problem/19832BOJ - 19832 - Configuration file문제 유형: 문자열 처리, 파싱, 스택, 해시문제 난이도: Gold IV시간 제한: 2초메모리 제한: 512MB 문제Vadim develops a parser for configuration files of his project. A configuration file consists of blocks delimited with braces: "{" marks the beginning of the block, and "}" marks the end of the block. Blocks can be nested. One block can contains several other bloc..

https://www.acmicpc.net/problem/5052BOJ - Phone List문제 유형: 문자열 처리, 트라이, 정렬문제 난이도: Gold IV 문제전화번호 목록이 주어진다. 이때, 이 목록이 일관성이 있는지 없는지를 구하는 프로그램을 작성하시오.전화번호 목록이 일관성을 유지하려면, 한 번호가 다른 번호의 접두어인 경우가 없어야 한다.예를 들어, 전화번호 목록이 아래와 같은 경우를 생각해보자긴급전화: 911상근: 97 625 999선영: 91 12 54 26이 경우에 선영이에게 전화를 걸 수 있는 방법이 없다. 전화기를 들고 선영이 번호의 처음 세 자리를 누르는 순간 바로 긴급전화가 걸리기 때문이다. 따라서, 이 목록은 일관성이 없는 목록이다. 입력첫째 줄에 테스트 케이스의 개수 t가 주..