넘치게 채우기

https://www.acmicpc.net/problem/2737 BOJ - 연속 합문제 유형: 수학, 정수론문제 난이도: Gold III시간 제한: 1초메모리 제한: 128MB 문제대부분의 양의 정수는 적어도 2개 이상의 연속된 자연수의 합으로 나타낼 수 있다.예를 들면 다음과 같다.6 = 1 + 2 + 39 = 5 + 4 = 4 + 3 + 2하지만, 8은 연속된 자연수 합으로 나타낼 수가 없다.자연수 N이 주어졌을 때, 이 수를 적어도 2개 이상의 연속된 자연수의 합으로 나타낼 수 있는 경우의 수를 출력하시오. 입력첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 정수 하나로 이루어져 있다. 이 정수는 문제에서 설명한 N이며, 231보다 작다. 출력각 테스트 케이스에 대해서 N을 적..

https://www.acmicpc.net/problem/14926 BOJ - Not Equal문제 유형: 오일러 경로, 그래프, dfs, 그리디, 백트래킹문제 난이도: Gold V시간 제한: 1초메모리 제한: 512MB 문제주어진 N개의 수가 모두 서로 다르다는 것은 기호 "!="를 통해 하나의 식으로 표현할 수 있다. 예를 들어 A, B, C가 모두 서로 다르다는 것은 논리식으로 (A != B) && (B != C) && (C != A) 로 쓸 수 있고, 이를 다음과 같이 한 줄로 표현하는 것을 A, B, C에 대한 "한 줄 표기법"이라고 부르기로 하자.A != B != C != A하지만 5개의 수 A, B, C, D, E가 모두 서로 다르다는 것을 다음처럼 표현하는 것은 올바른 한 줄 표기법이 아니..

https://www.acmicpc.net/problem/1507BOJ - 궁금한 민호문제 유형: 그래프, 최단경로, 플로이드-워셜문제 난이도: Gold II시간 제한: 2초메모리 제한: 128MB 문제강호는 N개의 도시로 이루어진 나라에 살고 있다. 각 도시는 M개의 도로로 연결되어 있으며, 각 도로를 지날 때 필요한 시간이 존재한다. 도로는 잘 연결되어 있기 때문에, 도시 A에서 B로 이동할 수 없는 경우는 존재하지 않는다.도시 A에서 도시 B로 바로 갈 수 있는 도로가 있거나, 다른 도시를 거쳐서 갈 수 있을 때, 도시 A에서 B를 갈 수 있다고 한다.강호는 모든 쌍의 도시에 대해서 최소 이동 시간을 구해놓았다. 민호는 이 표를 보고 원래 도로가 몇 개 있는지를 구해보려고 한다.예를 들어, 예제의 ..

https://www.acmicpc.net/problem/17501BOJ - 수식 트리문제 유형: 트리, 그래프, 그리디, 정렬문제 난이도: Gold II시간 제한: 1초메모리 제한: 256MB 문제수식 트리는 루트가 있는 이진 트리로 2N-1개의 노드가 있습니다. 1번부터 N번까지 노드는 피연산자 노드이며 다른 노드들은 연산자 노드이고 2N-1번 노드가 루트입니다.연산자 노드는 항상 두 개의 자식 노드를 가지며 연산자로 '+' 또는 '-' 를 가집니다.피연산자 노드는 아무 자식도 가지지 않고 하나의 정수를 가집니다.수식 트리의 계산은 다음과 같이 진행됩니다.2개의 피연산자 노드를 자식으로 가지는 연산자 노드를 하나 선택합니다.해당 노드의 연산자가 '+' 인 경우, 연산자 노드를 피연산자 노드로 바꾸고 ..

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의 너비를 가졌고, 양수의 길이를 가지고 있다. 기훈이 방은 직사각형 모양이고, 방 안에는 벽과 평행한 모양의 정사각형으로 나누어져 있다.이제 ‘-’와 ‘|’로 이루어진 바닥 장식 모양이 주어진다. 만약 두 개의 ‘-’가 인접해 있고, 같은 행에 있다면, 두 개는 같은 나무 판자이고, 두 개의 ‘|’가 인접해 있고,..