백준 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) 이므로 각 곱하기..

백준 15558 - 점프 게임시간 제한 2초, 메모리 제한 512MB# 조건상근이는 오른쪽 그림과 같은 지도에서 진행하는 게임을 만들었다.지도는 총 2개의 줄로 나누어져 있으며, 각 줄은 N개의 칸으로 나누어져 있다. 칸은 위험한 칸과 안전한 칸으로 나누어져 있고, 안전한 칸은 유저가 이동할 수 있는 칸, 위험한 칸은 이동할 수 없는 칸이다.가장 처음에 유저는 왼쪽 줄의 1번 칸 위에 서 있으며, 매 초마다 아래 세 가지 행동중 하나를 해야 한다.한 칸 앞으로 이동한다. 예를 들어, 현재 있는 칸이 i번 칸이면, i+1번 칸으로 이동한다.한 칸 뒤로 이동한다. 예를 들어, 현재 있는 칸이 i번 칸이면, i-1번 칸으로 이동한다.반대편 줄로 점프한다. 이때, 원래 있던 칸보다 k칸 앞의 칸으로 이동해야 한..

백준 16508 - 전공책시간 제한 1초, 메모리 제한 512MB# 조건곧 졸업을 앞둔 민호는 대학교 생활 동안 구매만 해놓고 한 번도 펴보지 않은 전공책에 먼지가 쌓여 있는 것을 보고는, 이 책들을 어떻게 처리해야 할지 고민 중이다. 열심히 고민한 끝에 민호는 결국 전공책을 모두 버리기로 마음먹었다. 하지만 그냥 버리기엔 심심한 민호는 전공책 제목에 있는 글자들을 오려서 단어 만들기 놀이를 하려고 한다. 단어 만들기 놀이는 아래 예시와 같다.1번 책 : COMPUTERARCHITECTURE (35,000원)2번 책 : ALGORITHM (47,000원)3번 책 : NETWORK (43,000원)4번 책 : OPERATINGSYSTEM (40,000원)만약 민호가 만들고 싶은 단어가 ALMIGHTY라고 ..

백준 11048 - 이동하기시간 제한 1초, 메모리 제한 256MB# 조건준규는 N×M 크기의 미로에 갇혀있다. 미로는 1×1크기의 방으로 나누어져 있고, 각 방에는 사탕이 놓여져 있다. 미로의 가장 왼쪽 윗 방은 (1, 1)이고, 가장 오른쪽 아랫 방은 (N, M)이다.준규는 현재 (1, 1)에 있고, (N, M)으로 이동하려고 한다. 준규가 (r, c)에 있으면, (r+1, c), (r, c+1), (r+1, c+1)로 이동할 수 있고, 각 방을 방문할 때마다 방에 놓여져있는 사탕을 모두 가져갈 수 있다. 또, 미로 밖으로 나갈 수는 없다.준규가 (N, M)으로 이동할 때, 가져올 수 있는 사탕 개수의 최댓값을 구하시오.# 접근 방법딱 보자마자 시간 초과를 안 당하기 위해서는 dp로 접근해야 겠다고 ..

백준 1747 - 소수&팰린드롬시간 제한 2초, 메모리 제한 256MB# 문제어떤 수와 그 수의 숫자 순서를 뒤집은 수가 일치하는 수를 팰린드롬이라 부른다. 예를 들어 79,197과 324,423 등이 팰린드롬 수이다.어떤 수 N (1 ≤ N ≤ 1,000,000)이 주어졌을 때, N보다 크거나 같고, 소수이면서 팰린드롬인 수 중에서, 가장 작은 수를 구하는 프로그램을 작성하시오.입력첫째 줄에 N이 주어진다.출력첫째 줄에 조건을 만족하는 수를 출력한다.# 접근 방법우선 소수를 구해주었다.이 때 주의할 점은 100001까지가 아닌, 1000000보다 크거나 같은 소수 중 팰린드롬인 수까지 구해야 하므로 여유있게 1500000까지 구해주었다.이후, bisect를 이용하여 N이 들어갈 index를 구해서 해당..

백준 - 2559_수열시간 제한 1초, 메모리 제한 128MB# 문제입력첫째 줄에는 두 개의 정수 N과 K가 한 개의 공백을 사이에 두고 순서대로 주어진다.첫 번째 정수 N은 온도를 측정한 전체 날짜의 수이다.N은 2 이상 100,000 이하이다.두 번째 정수 K는 합을 구하기 위한 연속적인 날짜의 수이다.K는 1과 N 사이의 정수이다.둘째 줄에는 매일 측정한 온도를 나타내는 N개의 정수가 빈칸을 사이에 두고 주어진다.이 수들은 모두 -100 이상 100 이하이다.출력첫째 줄에는 입력되는 온도와 수열에서 연속적인 K일의 온도의 합이 최대가 되는 값을 출력한다.# 접근 방법누적합과 투 포인터를 활용해주면 된다.우선 입력받은 온도의 누적합을 cumulative_sum에 저장해준 후 0번 인덱스에 0을 삽입해..