시간 제한메모리 제한2초512MB문제성관이는 다음과 같은 성질을 만족하는 배열을 좋아한다. 배열의 길이는 N이다.배열에 채워져있는 수는 1보다 크거나 같고, K보다 작거나 같은 자연수이다.배열에서 연속한 수가 A와 B일 때, A 예를 들어, N = 4, K = 7인 경우에 [1, 7, 7, 2]는 성관이가 좋아하는 배열이다. 모든 연속한 수가 1 N과 K가 주어졌을 때, 성관이가 좋아하는 배열의 경우의 수를 구하는 프로그램을 작성하시오.입력첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 10, 1 ≤ K ≤ 100,000) 출력첫째 줄에 성관이가 좋아하는 배열의 개수를 1,000,000,007로 나눈 나머지를 출력한다. 풀이성관이가 좋아하는 배열의 세 번째 조건을 그대로 사용하지 않고 부정을 취하는 것이..

시간 제한메모리 제한1초512MB문제취준생 주헌이는 드디어 취업에 성공했다. 주헌이가 취직한 회사는 비대면 전자계약 서비스 모두싸인(MODUSIGN) 이라는 회사이다. 그리고 오늘은 첫 출근날이다. 주헌이의 출근길에는 다리가 있는데, 전날에 비가 많이 오는 바람에 다리가 끊어져 판자 여러 개로 쪼개져 버렸다. 주헌이는 무사히 회사에 도착할 수 있을까? 다리는 수직선으로 나타낼 수 있으며, 각 판자는 구간 [ L, R ]의 범위에 놓여 있다. 주헌이는 0에서 출발하여 오른쪽(양의 방향)으로만 이동한다. 판자로 덮인 좌표는 자유롭게 건너갈 수 있다. 하지만 판자로 덮이지 않은 좌표는 오직 주헌이가 점프를 해야만 건너갈 수 있으며, 점프를 할 경우 착지한 위치에 판자가 놓여 있어야 한다. 판자의 양 끝점에도 ..

시간 제한메모리 제한0.25초512MB문제2차원 좌표 평면 위의 두 선분 L1, L2가 주어졌을 때, 두 선분이 교차하는지 아닌지 구해보자. 한 선분의 끝 점이 다른 선분이나 끝 점 위에 있는 것도 교차하는 것이다. L1의 양 끝 점은 (x1, y1), (x2, y2), L2의 양 끝 점은 (x3, y3), (x4, y4)이다. 입력첫째 줄에 L1의 양 끝 점 x1, y1, x2, y2가, 둘째 줄에 L2의 양 끝 점 x3, y3, x4, y4가 주어진다. 출력L1과 L2가 교차하면 첫째 줄에 1, 아니면 0을 출력한다. 두 선분이 한 점에서 교차하는 경우 둘째 줄에 교차하는 점의 x좌표와 y좌표를 공백으로 구분해 출력한다. 한 점에서 교차하지 않는 경우에는 둘째 줄을 출력하지 않는다. 좌표의 절대/상대..

시간 제한메모리 제한2초1024MB문제에릭은 방학 동안 너무 심심한 나머지, 당근 클릭 게임이라는 게임을 직접 만들어서 플레이하기로 했다. 이 게임에서 초기에 에릭은 당근을 0개 가지고 있고, s가 1인 상태로 게임을 시작한다.그 후, 매초 다음 두 가지의 행동 중 하나를 할 수 있다.마우스를 클릭하고 당근을 s개 얻는다.정수 i (1 ≤ i ≤ N)를 고르고, 당근 Ai개를 지불하여 i번째 스피드 효과를 구매한다. 구매 직후, s가 Bi만큼 증가한다. (이전에 구매한 스피드 효과를 다시 구매하는 것도 가능하다.)게임을 개발하느라 에너지를 모두 소모해 버린 에릭을 위해 게임을 K초 플레이한 후 당근을 최대 몇 개까지 가지고 있을 수 있는지 알려주자!입력첫 번째 줄에 두 정수 N, K가 공백으로 구분되어 ..

선분은 직선 상의 두 점과 그 두 점 사이의 점들로 구성되는 유한인 직선의 부분이다. 간단히 두 점을 잇는 최단거리다. 샤프심 두 개를 책상에 쏟았다. 샤프심을 선분이라고 봤을 때 이 두 가닥의 샤프심의 위치관계를 몇 가지로 나누어 설명할 수 있을까. 우선 두 샤프심이 서로 닿은 경우와 닿지 않은 경우가 있을 것이다. 그리고 닿은 경우에는 겹친 경우도 있을 것이다. 닿지 않은 경우도 나란히 놓여서 샤프심의 길이가 무한히 늘어나도 닿지 않는 특수한 경우와 그렇지 않은 경우로 나눌 수 있다. 1. 벡터의 외적 벡터는 고등수학에 따르면 크기와 방향을 가진 물리량을 의미한다. 쉽게 생각하면 화살표로 볼 수 있다. 길이도 있고 방향도 있다. 선분끼리는 더하거나 뺀다는 연산을 길이만 두고 할 수 있으나 벡터는 방향..

분리 집합은 두 집합의 관계르 나타내는 것으로 두 집합 A와 B의 교집합이 공집합일 때 A와 B는 분리 집합이라고 한다. 집합의 요소를 놓고 요소들이 포함된 집합이 같은 집합인지 분리 집합인지 확인하고, 두 분리 집합을 하나로 병합하는 알고리즘을 유니온 파인드라고 한다. 1. 분리 집합(Disjoint set) 두 집합 A = {1, 2, 3, 4, 5}와 B = {5, 6, 7, 8, 9}는 '5'를 공통 원소로 갖는다. 이 경우 A, B는 분리 집합이 아니다. 집합 C = {10, 11, 12, 13, 14}가 있을 때, A∪B와 C는 공통 원소가 없는 분리 집합이다. A와 C도 분리 집합이고 B와 C도 분리 집합이다. 여러 정점을 놓고 간선으로 연결한 상태가 주어졌을 때, 정점과 간선을 거쳐 연결된..

시간 제한메모리 제한1초128MB문제어떤 도시의 중심가는 N개의 동서방향 도로와 N개의 남북방향 도로로 구성되어 있다. 모든 도로에는 도로 번호가 있으며 남북방향 도로는 왼쪽부터 1에서 시작하여 N까지 번호가 할당되어 있고 동서방향 도로는 위부터 1에서 시작하여 N까지 번호가 할당되어 있다. 또한 동서방향 도로 사이의 거리와 남 북방향 도로 사이의 거리는 모두 1이다. 동서방향 도로와 남북방향 도로가 교차하는 교차로의 위치는 두 도로의 번호의 쌍인 (동서방향 도로 번호, 남북방향 도로 번호)로 나타낸다. N이 6인 경우의 예를 들면 다음과 같다.이 도시에는 두 대의 경찰차가 있으며 두 차를 경찰차1과 경찰차2로 부른다. 처음에는 항상 경찰차1은 (1, 1)의 위치에 있고 경찰차2는 (N, N)의 위치에 ..

최장 증가 부분 수열 - 나무위키 어떤 임의의 수열이 주어질 때, 이 수열에서 몇 개의 수들을 제거해서 부분수열을 만들 수 있다. 이때 만들어진 부분수열 중 오름차순으로 정렬된 가장 긴 수열을 최장 증가 부분 수열이라 한다. namu.wiki 1. 최장 증가 부분 수열(LIS) LIS 문제를 처음 봤을 때 만능 문제해결 툴 브루트포스를 떠올렸는데 당연히 죽음뿐. LIS 문제의 정해는 보통 두 가지다. O(N2)으로 해결할 수 있는 다이나믹 프로그래밍, O(NlogN)으로 해결할 수 있는 이진 탐색이다. 여기서 또 이진 탐색 해법이 있다는 걸 처음 알았을 때는 "대체 이게 뭔소리냐" 싶었는데 잘 살펴보고 직접 구현해보면 그렇게 어려운 개념은 아니다. 하지만 이 문제를 이미 몇 년 전에 처음 접해서 풀었던 ..