https://www.acmicpc.net/problem/17291너무 어렵게 생각했다. 2차원 배열까지 생각할 필요 없다.짝수 일, 홀수 일 기준으로 X일 전에 몇 마리가 죽는 지를 체크하자.제목새끼치기 조건시간 제한 : 1 초메모리 제한 : 256 MB 문제실험실에서 새로운 종의 벌레 한 마리가 탄생하였다. 벌레는 스스로 분열하며, 분열하면 자기 자신과 같은 벌레를 한 마리 만들어 내게 된다. 벌레가 분열하는 규칙은 다음과 같다. 벌레는 기준년도 1년 2월에 1마리가 탄생한다. 벌레는 매년 1월이 되면 분열한다. 분열시 본래의 개체는 그대로, 새로운 개체가 하나 탄생하는 것으로 본다. 홀수년도에 탄생한 개체는 3번 분열시, 짝수년도에 탄생한 개체는 4번 분열시 사망한다. 예를 들어, 기준년도 1년 2..
https://www.acmicpc.net/problem/23830 이분탐색+K가 양의 정수, 즉 자연수를 말하고 0은 포함되지 않는다제목제기차기조건시간 제한 : 1 초메모리 제한 : 512 MB문제얼마 전 학교 체육대회 "사차원"이 열렸다. 대회 종목 중 하나는 제기차기였고, 몇몇 학생을 제외하고는 대부분의 학생이 한두 번 밖에 차지 못했다. 잘 하는 사람과 못 하는 사람의 점수 차이가 너무 커졌기 때문에, 대회 전체 점수에 영향이 클 거라고 생각한 선생님은 다음과 같은 규칙을 정했다.기준이 되는 양의 정수 K를 정한다.어떤 학생의 제기차기 점수가 K+r 초과라면 그 학생의 점수에서 p를 뺀다.어떤 학생의 제기차기 점수이 K 미만이라면 그 학생의 점수에 q를 더한다.선생님은 이 규칙으로 점수를 계산..
27212번: 미팅 오늘은 A대학의 학생 $N$명과 B대학의 학생 $M$명이 만나는 날이다. 이들이 만나는 장소에는 크고 길이가 긴 식탁이 하나 있어서, 한쪽에는 A대학 학생이, 다른 한쪽에는 B대학 학생이 앉을 예정이 www.acmicpc.net dp[i][j] = dp[i - 1][j - 1] + W[A[i]][B[j]]; dp[i][j] = Math.max(dp[i][j], dp[i - 1][j]); dp[i][j] = Math.max(dp[i][j], dp[i][j - 1]); 제목 미팅 조건 시간 제한 : 1 초 메모리 제한 : 512 MB 문제 오늘은 A대학의 학생 N명과 B대학의 학생 M명이 만나는 날이다. 이들이 만나는 장소에는 크고 길이가 긴 식탁이 하나 있어서, 한쪽에는 A대학 학생이,..
31477번: 양갈래 구하기 다음 그림에서 1과 2를 연결하는 덩굴, 3과 6을 연결하는 덩굴, 3과 7을 연결하는 덩굴을 자르면 총 3+1+2로 6의 힘이 최솟값이 된다. www.acmicpc.net N개의 방이 존재하고 N-1개의 각 방을 잇는 덩굴이 존재하며 각 방끼리 무조건 이동 가능 = 사이클이 생길 수 없는 구조 DFS를 통한 최소 두께를 갱신하여 합 제목 양갈래 구하기 조건 시간 제한 : 1 초 메모리 제한 : 1024 MB 문제 평화로운 양갈래의 마을에 위기가 닥쳐왔다! 덩굴에 독이 퍼져 양갈래가 있는 곳으로 옮겨지고 있다! 독은 양갈래의 방을 제외하고, 정확히 한 개의 덩굴로 연결된 방에서부터 옮겨진다. 모든 방의 쌍 사이에는 1개 이상의 덩굴을 지나는 유일한 경로가 존재하며, 덩굴은 총..
25307번: 시루의 백화점 구경 첫째 줄에 백화점의 세로 길이, 가로 길이, 마네킹과 떨어져야 하는 거리를 의미하는 정수 $N, M, K$가 공백으로 구분되어 주어진다. ($1 \leq N,M \leq 2\,000$, $0 \leq K \leq 4\,000$) 둘째 줄부터 $N$개의 줄 www.acmicpc.net 각 점의 영역을 표시해야할 때 각 점을 동시에 BFS Multi-Source BFS 제목 시루의 백화점 구경 조건 시간 제한 : 2 초 메모리 제한 : 1024 MB 문제 시루는 부모님과 함께 백화점에 갔다. 부모님은 쇼핑할 것이 많기 때문에 여러 곳을 돌아다녀야 하고, 시루는 부모님과 함께 걸어다니는 것이 너무 힘들어서 의자에 앉아서 쉬려고 한다. 백화점은 세로 길이가 N, 가로 길이가 M..
30640번: 운전 연습 장롱 면허를 보유한 시은이는 수직선 위에서 운전 연습을 하려고 한다. 시은이는 원점에서 출발하여 항상 양의 방향으로 이동할 것이다. 자동차는 단위 거리 1만큼 이동하는데 전기 1kWh를 소모 www.acmicpc.net 해당 위치까지 갈 수 있다는 것은 마법사를 만나도 0번째 위치로 이동해서 다시 올 수 있다 해당 위치까지 갈 수 없다는 것은 마법사를 만나도 다시 올 수 없다 순간이동을 해서 다시 올 수 있음은 다음 조건으로 확인할 수 있다 순간이동한 곳까지 Cost = A 마법사를 만난 곳까지 Cost = B A B 일 경우 A - B < B 이어야만 가능 제목 운전 연습 조건 시간 제한 : 1 초 메모리 제한 : 1024 MB 문제 장롱 면허를 보유한 시은이는 수직선 위에서 ..
30680번: 별자리 만들기 첫째 줄에 장식의 개수 $N$이 정수로 주어진다. $(1 \leq N \leq 100 \, 000)$ 둘째 줄부터는 $N$개의 장식에 대한 정보가 스타가 받는 순서대로 주어진다. 각 장식에 대해서 첫째 줄에는 별의 개수 $A_i$가 www.acmicpc.net DFS + PriorityQueue 제목 별자리 만들기 조건 시간 제한 : 1 초 메모리 제한 : 512 MB 문제 밤하늘에 무지갯빛 별이 하나 반짝이고 있다. 이 무지갯빛 별과 N개의 장식을 사용해서 별자리를 만들어 밤하늘을 예쁘게 꾸미려고 한다. 각 장식의 특징은 다음과 같다. 각 장식은 Ai개의 별과 (Ai-1)개의 실로 이루어진 트리다. 실은 서로 다른 두 별을 연결한다. 각 장식에는 정확히 1개의 붉은색 별이 ..
25395번: 커넥티드 카 실험 실험 결과로 나올 수 있는 사물 인터넷에 연결된 커넥티드 카들의 조합은 $\{1,2,3\}$, $\{2,3\}$, $\{3\}$, $\{3,4\}$가 있다. www.acmicpc.net 두 포인터 + BFS 제목 커넥티드 카 실험 조건 시간 제한 : 2 초 메모리 제한 : 1024 MB 문제 정보통신기술(ICT)의 발달에 힘입어, 미래형 자동차로 여겨졌던 인터넷 연결을 통해 운전자에게 다양한 서비스를 제공하는 커넥티드 카(connected car)가 현실로 다가왔다. 현대오토에버는 이에 발맞춰 클라우드와 사물 인터넷을 비롯한 최신 ICT를 적용한 차세대 커넥티드 카 서비스 플랫폼을 구축하고, 최고의 커넥티드 카를 완성하기 위한 핵심 소프트웨어 기술을 축적하고 있다. 현대오..
31410번: 제독 작전 부대에 미확인 오염 물질이 발생해 위기에 빠졌다! 오염 물질은 부대 내의 수직선 위의 서로 다른 $N$개의 위치에 발생했으며, 그중 $i$번째 오염 물질의 오염도는 $p_i$이며 $x_i$ 위치에 발생했다. www.acmicpc.net 한 쪽 끝에서 시작해야 불필요한 경로 중복을 없앨 수 있다 왼쪽 끝과 오른쪽 끝에서 시작 1번째와 N번째를 남겨둘 때는 기준이 달라지기 때문에 기존에 구한 방식과 다르게 따로 구해줘야 한다 제목 제독 작 조건 시간 제한 : 1 초 메모리 제한 : 1024 MB 문제 부대에 미확인 오염 물질이 발생해 위기에 빠졌다! 오염 물질은 부대 내의 수직선 위의 서로 다른 N개의 위치에 발생했으며, 그중 i번째 오염 물질의 오염도는 pi이며 xi 위치에 발생했..
23286번: 허들 넘기 첫째 줄에 세 정수 N, M, T가 주어진다. 다음 M개의 줄에 그래프 간선의 정보 u, v, h가 주어지고, u에서 v로 가는 간선이 있고, 높이가 h인 허들이 간선 중간에 놓여 있다는 의미이다. 마지막 T개의 www.acmicpc.net Minimum 다익스트라 제목 허들 넘기 조건 시간 제한 : 2 초 메모리 제한 : 1024 MB 문제 허들 국가대표를 꿈꾸는 연두는 그래프 위에서 허들 넘기를 연습하려고 한다. 연두가 연습할 그래프는 정점이 N개 있고, 간선이 M개 있다. 간선은 방향성이 있어, 1에서 2로 가는 길이 있더라도, 2에서 1로 가는 길은 없을 수도 있다. 간선 위에는 허들이 중간에 놓여 있고, 간선을 지나갈 때는 반드시 허들을 넘어야 한다. 연두는 연습을 T번..
1766번: 문제집 첫째 줄에 문제의 수 N(1 ≤ N ≤ 32,000)과 먼저 푸는 것이 좋은 문제에 대한 정보의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 둘째 줄부터 M개의 줄에 걸쳐 두 정수의 순서쌍 A,B가 빈칸을 사이에 두고 주 www.acmicpc.net 위상정렬 제목 문제 조건 시간 제한 : 2 초 메모리 제한 : 128 MB 문제 민오는 1번부터 N번까지 총 N개의 문제로 되어 있는 문제집을 풀려고 한다. 문제는 난이도 순서로 출제되어 있다. 즉 1번 문제가 가장 쉬운 문제이고 N번 문제가 가장 어려운 문제가 된다. 어떤 문제부터 풀까 고민하면서 문제를 훑어보던 민오는, 몇몇 문제들 사이에는 '먼저 푸는 것이 좋은 문제'가 있다는 것을 알게 되었다. 예를 들어 1번 문제를 풀고 ..
31230번: 모비스터디 첫 번째 테스트 케이스에 대한 그림이다. 이 테스트 케이스에는 $1 → 7 → 2 → 6$ 경로와 $1 → 4 → 5 → 2 → 6$ 경로 총 2개의 최단 경로가 존재하며, 최단 경로 위에 존재하는 도시는 $1$, $2$, $4$, $5 www.acmicpc.net X는 최단경로에 있다 = (1-X 거리 + X-N 거리) 가 최단거리다 다익스트라에서 현재 위치의 거리를 최단거리로 만드려고 하는 CURR의 값이 최적이 아닌 경우 NEXT와 상관없이 최적이 될 수 없으므로 CONTINUE로 경우를 제외해야한다. 제목 모비스터디 조건 시간 제한 : 2 초 메모리 제한 : 1024 MB 문제 현대모비스는 글로벌 자동차 부품 기업으로 자율주행, 커넥티비티, 전동화 분야에 역량을 집중해 스..
