백준 30804 - 과일 탕후루시간 제한 2초, 메모리 제한 1024MB# 조건은하는 긴 막대에 $N$개의 과일이 꽂혀있는 과일 탕후루를 만들었습니다. 과일의 각 종류에는 $1$부터 $9$까지의 번호가 붙어있고, 앞쪽부터 차례로 $S_1, S_2, \cdots, S_N$번 과일이 꽂혀있습니다. 과일 탕후루를 다 만든 은하가 주문을 다시 확인해보니 과일을 두 종류 이하로 사용해달라는 요청이 있었습니다.탕후루를 다시 만들 시간이 없었던 은하는, 막대의 앞쪽과 뒤쪽에서 몇 개의 과일을 빼서 두 종류 이하의 과일만 남기기로 했습니다. 앞에서 $a$개, 뒤에서 $b$개의 과일을 빼면 $S_{a+1}, S_{a+2}, \cdots, S_{N-b-1}, S_{N-b}$번 과일, 총 $N-(a+b)$개가 꽂혀있는 탕후..

백준 10711 - 모래성시간 제한 1초, 메모리 제한 256MB# 조건명우가 만든 모래성을 2차원 격자단위로 만들었으며, 각 격자마다 튼튼함의 정도를 다르게 해서 성을 만들었다. 이 튼튼함은 1부터 9 사이의 숫자로 표현될 수 있다. 이 튼튼함은, 자기 격자 주변의 8방향 (위 아래 왼쪽 오른쪽, 그리고 대각선) 을 봐서 모래성이 쌓여있지 않은 부분의 개수가 자기 모래성의 튼튼함보다 많거나 같은 경우 파도에 의해서 무너질 수 있음을 의미한다. 그 이외의 경우는 파도가 쳐도 무너지지 않는다. 모래성이 무너진 경우, 그 격자는 모래성이 쌓여있지 않은 것으로 취급한다.이 모래성은 언젠가는 파도에 의해서 깎이고 깎여서, 결국 한가지 형태로 수렴할 것이다. 모래성을 완성한 명우는 문득 자신이 만든 예술품의 수명..

백준 2824 - 최대공약수시간 제한 1초, 메모리 제한 192MB# 조건상근이는 학생들에게 두 양의 정수 A와 B의 최대공약수를 계산하는 문제를 내주었다. 그런데, 상근이는 학생들을 골탕먹이기 위해 매우 큰 A와 B를 주었다.상근이는 N개의 수와 M개의 수를 주었고, N개의 수를 모두 곱하면 A, M개의 수를 모두 곱하면 B가 된다.이 수가 주어졌을 때, 최대공약수를 구하는 프로그램을 작성하시오.입력첫째 줄에 N(1 ≤ N ≤ 1000)이 주어진다. 둘째 줄에는 N개의 양의 정수가 공백으로 구분되어 주어진다. 이 수는 모두 1,000,000,000보다 작고, N개의 수를 곱하면 A가 된다.셋째 줄에 M(1 ≤ M ≤ 1000)이 주어진다. 넷째 줄에는 M개의 양의 정수가 공백으로 구분되어 주어진다. 이..

백준 15655 - N과 M(6)시간 제한 1초, 메모리 제한 512MB# 조건N개의 자연수와 자연수 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. N개의 자연수는 모두 다른 수이다.N개의 자연수 중에서 M개를 고른 수열고른 수열은 오름차순이어야 한다.입력첫째 줄에 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 8)둘째 줄에 N개의 수가 주어진다. 입력으로 주어지는 수는 10,000보다 작거나 같은 자연수이다.출력한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다.중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다.수열은 사전 순으로 증가하는 순서로 출력해야 한다.# 접근 방법전형적인 백트래킹 문제이다.조합을 사용하여 ..

백준 11663 - 선분 위의 점시간 제한 1초, 메모리 제한 256MB# 조건일차원 좌표상의 점 N개와 선분 M개가 주어진다. 이때, 각각의 선분 위에 입력으로 주어진 점이 몇 개 있는지 구하는 프로그램을 작성하시오.입력첫째 줄에 점의 개수 N과 선분의 개수 M이 주어진다. (1 ≤ N, M ≤ 100,000) 둘째 줄에는 점의 좌표가 주어진다. 두 점이 같은 좌표를 가지는 경우는 없다. 셋째 줄부터 M개의 줄에는 선분의 시작점과 끝점이 주어진다. 입력으로 주어지는 모든 좌표는 1,000,000,000보다 작거나 같은 자연수이다.# 접근 방법주어지는 좌표가 10억 이하이므로 각 점을 리스트에 기록하며 값을 더하는 것은 시간, 메모리적으로도 말이 안된다.따라서, 주어진 점을 오름 차순으로 정렬해준 후 이..

백준 21921 - 블로그시간 제한 1초, 메모리 제한 512MB# 조건찬솔이는 블로그를 시작한 지 벌써 $N$일이 지났다.요즘 바빠서 관리를 못 했다가 방문 기록을 봤더니 벌써 누적 방문 수가 6만을 넘었다.찬솔이는 $X$일 동안 가장 많이 들어온 방문자 수와 그 기간들을 알고 싶다.찬솔이를 대신해서 $X$일 동안 가장 많이 들어온 방문자 수와 기간이 몇 개 있는지 구해주자.# 접근 방법누적 합을 구해준 후 x일만큼의 방문자 수로 기록해준다.만약 x가 2이고 [1, 2, 3, 4, 5]의 방문자 수가 있다면 누적 합 [1, 3, 6, 10, 15]를 구해주고 기간마다의 합을 구해준다.[0, 4, 5, 7, 9]를 구한 후 최댓 값과 카운트를 구해준다.import sys sys.stdin = open(..

백준 2115 - 갤러리시간 제한 2초, 메모리 제한 128MB# 조건갤러리의 지도는 M*N의 정사각형 격자로 표현될 수 있다.어떤 정사각형들은 벽으로 구성되어 있고, 다른 정사각형들은 빈 공간으로 구성되어 있다.벽을 회색, 빈 공간을 흰색으로 표현하면 다음 그림과 같다.갤러리에 그림을 걸려고 한다.그림의 길이는 정사각형의 변의 길이의 두 배이다.반드시 빈 공간과 인접해 있는 벽에만 그림을 걸 수 있으며, 그림들은 서로 겹칠 수 없다.갤러리의 맵이 주어졌을 때, 최대로 걸 수 있는 그림의 개수를 출력하는 프로그램을 작성하시오.입력첫째 줄에 갤러리의 세로 길이 M과 가로 길이 N이 주어진다. (1 ≤ M, N ≤ 1,000)다음 M개의 줄에는 각각 N개의 문자가 주어진다.문자는 'X' 또는 '.'이며 'X..

백준 1743 - 음식물 피하기시간 제한 2초, 메모리 제한 128MB# 조건코레스코 콘도미니엄 8층은 학생들이 3끼의 식사를 해결하는 공간이다. 그러나 몇몇 비양심적인 학생들의 만행으로 음식물이 통로 중간 중간에 떨어져 있다. 이러한 음식물들은 근처에 있는 것끼리 뭉치게 돼서 큰 음식물 쓰레기가 된다. 이 문제를 출제한 선생님은 개인적으로 이러한 음식물을 실내화에 묻히는 것을 정말 진정으로 싫어한다. 참고로 우리가 구해야 할 답은 이 문제를 낸 조교를 맞추는 것이 아니다. 통로에 떨어진 음식물을 피해가기란 쉬운 일이 아니다. 따라서 선생님은 떨어진 음식물 중에 제일 큰 음식물만은 피해 가려고 한다. 선생님을 도와 제일 큰 음식물의 크기를 구해서 “10ra"를 외치지 않게 도와주자.입력첫째 줄에 통로의 ..

백준 13699 - 점화식시간 제한 5초, 메모리 제한 512MB# 조건다음의 점화식에 의해 정의된 수열 t(n)을 생각하자:t(0)=1t(n)=t(0)t(n-1)+t(1)t(n-2)+...+t(n-1)*t(0)이 정의에 따르면,t(1)=t(0)*t(0)=1t(2)=t(0)t(1)+t(1)t(0)=2t(3)=t(0)t(2)+t(1)t(1)+t(2)*t(0)=5...주어진 입력 0 ≤ n ≤ 35에 대하여 t(n)을 출력하는 프로그램을 작성하시오.입력첫째 줄에 n(0출력첫째 줄에 t(n)을 출력한다.# 접근 방법점화식을 있는 그대로 구현해주면 된다.t[0] = 1로 설정해준 뒤 1부터 N+1까지 for문을 돌린다.t(n)=t(0)t(n-1)+t(1)t(n-2)+...+t(n-1)*t(0) 이므로 각 곱하기..