시간 제한메모리 제한1.2초1024MB문제(요약함)0번 항이 1, 1번항이 1로 시작되는 피보나치 수열을 두고 길이 N의 수열A에 대한 쿼리가 주어진다. 수열 A는 초기에 모든 값이 0으로 되어있으며 첫 번째 항을 1번 항, 마지막 항을 N번 항으로 한다. 쿼리는 l, r로 N이하인 두 개의 자연수로 주어진다. l은 항상 r이하임이 보장된다. 쿼리는 수열 A의 l번 항부터 r번 항을 피보나치 수열의 1번 항부터 r-l+1번 항까지로 바꾸는 작업이다. 입력첫째 줄에는 수열의 크기 N이 주어진다. N은 100만 이하의 자연수이다.둘째 줄에는 쿼리의 수 Q가 주어진다. Q는 100만 이하의 자연수이다.셋째 줄 부터 Q줄에 걸친 쿼리가 주어진다. 출력모든 쿼리를 순서대로 적용한 후 수열 A의 모든 항을 공백으로..

시간 제한메모리 제한1초1024MB문제종민이는 CTP 초등학교 5학년 3반 담임 교사로 일하고 있다. 최근 들어 CTP 초등학교에 전학을 오는 5학년 학생들이 많아져서, 대책으로 종민이가 담당하는 3반을 2개 분반으로 나누기로 했다. 종민이는 이전부터 자신이 담당하는 반의 학생들로부터 고통을 받고 있었다. 5학년 3반 친구들은 수업 시간임에도 불구하고 친구들끼리 놀면서 수업을 듣기를 거부하는 일이 많기 때문에, 5학년 3반의 분반은 종민이에게 매우 희소식이었다. 종민이는 5학년 3반의 모든 친한 친구인 두 학생을 서로 다른 분반에 배치하여 고통을 줄이려고 한다. 하지만 그런 배치가 불가능한 경우도 있기 때문에, 이를 위해 한가지 묘책을 생각해 냈다. 그것은 바로 친한 친구 관계인 두 학생이 서로 험담을 ..

시간 제한메모리 제한2초1024MB문제통학러 재헌이는 1교시 수업을 듣기 위해 아침 일찍 학교에 가려고 한다. 재헌이가 사는 지역은 크기가 N * M 인 격자로 나타낼 수 있는데, i행 j열에 해당하는 칸을 (i, j)로 나타낼 때 재헌이는 현재 (1, 1)에, 학교는 (N, M)에 위치해 있다. 재헌이는 상하좌우로 한 칸씩 이동할 수 있고 지역 바깥으로 나갈 수는 없다.등굣길은 순탄치만은 않은데, 이 지역에는 K개의 정체 구역이 있다. i번째 정체 구역은 세 정수 Ri, Ci, Di로 표현되며, 이는 (Ri, Ci)로부터 거리가 Di 이하인 칸들에는 극심한 교통 정체가 일어나고 있음을 의미한다. 두 칸 (R1, C1), (R2, C2) 사이의 거리는 |R1 - R2| + |C1 - C2|와 같다.재헌이..

시간 제한메모리 제한1초1024MB문제 입력 출력첫째 줄에 d의 최댓값을 출력한다. 풀이총 N-1개의 길만 골라야 한다. 모든 길의 정보를 받으면서 가장 먼저 여는 가게의 정보를 기억해둔다. 그 길에 연결된 학원부터 탐색을 시작한다. 학원 u를 탐색하기 시작하면 연결된 v들과 그 길 위에 t를 확인해 가장 먼저 여는 노점이 있는 길을 선택한다. 그런데 만약 v와 u가 이미 선택된 길들로 이동이 가능한 상태라면 선택하지 않는다. 만약 N-1개의 길을 잘 선택해서 N일까지 키위새가 죽지 않는다고 해보자. 도중에 어떤 탐색에서라도 u와 v가 이미 이동가능한 경로가 선택된 상태라면 사이클이 생겨나게 되고 N-1개의 길을 어떻게 선택하더라고 N개의 학원을 모두 갈 수 없게 된다. 문제에서 원하는 조건은 모든 학원..

시간 제한메모리 제한1초512MB문제학부 연구생으로 새로 연구실에 들어온 민상이는 사용할 자리를 정하려고 한다.연구실은 격자 모양으로 되어있고 에어컨에서 바람이 상,하,좌,우 4방향으로 분다. 물론 에어컨이 위치한 곳에도 바람이 분다.민상이는 더위를 많이 타서 에어컨 바람이 지나가는 곳 중 하나를 선택하여 앉으려고 한다.연구실에는 다양한 물건들이 있어 바람의 방향을 바꾼다.연구실에 있는 물건의 종류는 총 4가지가 있다. 아래 화살표의 의미는 바람이 각 물건에서 바람의 이동을 표시한 것이다.연구실 어디든 민상이가 앉을 수 있는 자리이다. 즉 에어컨이 위치한 자리와 물건이 있는 자리 모두 앉을 수 있다.민상이가 원하는 자리는 몇 개 있는지 계산해주자. 입력첫 번째 줄에는 연구실의 크기가 세로 N(1 ≤ N ..

시간 제한메모리 제한초MB문제N보다 작거나 같은 자연수 중에서, 집합 K의 원소로만 구성된 가장 큰 수를 출력하는 프로그램을 작성하시오. K의 모든 원소는 1부터 9까지의 자연수로만 구성된다. 예를 들어 N=657이고, K={1, 5, 7}일 때 답은 577이다. 입력첫째 줄에 N, K의 원소의 개수가 공백을 기준으로 구분되어 자연수로 주어진다. (10 ≤ N ≤ 100,000,000, 1 ≤ K의 원소의 개수 ≤ 3) 둘째 줄에 K의 원소들이 공백을 기준으로 구분되어 주어진다. 각 원소는 1부터 9까지의 자연수다. 단, 항상 K의 원소로만 구성된 N보다 작거나 같은 자연수를 만들 수 있는 경우만 입력으로 주어진다. 출력첫째 줄에 N보다 작거나 같은 자연수 중에서, K의 원소로만 구성된 가장 큰 수를 출..

시간 제한메모리 제한1초128MB문제대부분의 양의 정수는 적어도 2개 이상의 연속된 자연수의 합으로 나타낼 수 있다.예를 들면 다음과 같다.6 = 1 + 2 + 39 = 5 + 4 = 4 + 3 + 2하지만, 8은 연속된 자연수 합으로 나타낼 수가 없다.자연수 N이 주어졌을 때, 이 수를 적어도 2개 이상의 연속된 자연수의 합으로 나타낼 수 있는 경우의 수를 출력하시오. 입력첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 정수 하나로 이루어져 있다. 이 정수는 문제에서 설명한 N이며, 231보다 작다. 출력각 테스트 케이스에 대해서 N을 적어도 2개 이상의 연속된 자연수의 합으로 나타내는 경우의 수를 출력한다. 풀이N의 범위가 점심을 나가서 먹고 있기 때문에 브루트포스와 같은 방법은 ..

시간 제한메모리 제한2초128MB문제캡틴 이다솜은 자신의 해적선에 적을 공격하기 위한 대포알을 많이 보관해 놓는다. 다솜이는 미적감각이 뛰어나기 때문에, 대포알은 반드시 사면체 모양으로 쌓아놓아야 한다고 생각한다. 사면체를 만드는 방법은 길이가 N인 정삼각형 모양을 만든다. 그 위에 길이가 N-1인 정삼각형 모양을 얹고 그위에 계속 해서 얹어서 1크기의 정삼각형 모양을 얹으면 된다. 예를 들어, 사이즈가 3크기의 한 더미 모양은 다음과 같다.    X    X  X  X    X  X  XX  X  X각각의 삼각형은 1, 3, 6, 10 ,..... 와 같이 대포알을 가지고 있다. 따라서 완벽하게 쌓았을 때, 한 사면체에는 1, 4, 10, 20 ,.... 개를 가지고 있을 것이다. 현재 다솜이의 해적선..