복습노트 복습노트

문제 12869번: 뮤탈리스크 1, 3, 2 순서대로 공격을 하면, 남은 체력은 (12-9, 10-1, 4-3) = (3, 9, 1)이다. 2, 1, 3 순서대로 공격을 하면, 남은 체력은 (0, 0, 0)이다. www.acmicpc.net SCV가 최대 n명 주어진다. 뮤탈리스크가 공격을 할 때, 한 번에 세 개의 SCV를 공격할 수 있다. 첫 번째로 공격받는 SCV는 체력 9를 잃는다. 두 번째로 공격받는 SCV는 체력 3을 잃는다. 세 번째로 공격받는 SCV는 체력 1을 잃는다. SCV의 체력이 0 또는 그 이하가 되어버리면, SCV는 그 즉시 파괴된다. 한 번의 공격에서 같은 SCV를 여러 번 공격할 수는 없다. 남아있는 SCV의 체력이 주어졌을 때, 모든 SCV를 파괴하기 위해 공격해야 하는 횟..

문제 1339번: 단어 수학 첫째 줄에 단어의 개수 N(1 ≤ N ≤ 10)이 주어진다. 둘째 줄부터 N개의 줄에 단어가 한 줄에 하나씩 주어진다. 단어는 알파벳 대문자로만 이루어져있다. 모든 단어에 포함되어 있는 알파벳은 최대 www.acmicpc.net n개의 영어 대문자로 주어진 문자열이 주어진다. 문자열의 알파벳에 0 ~ 9 까지의 숫자를 부여한뒤 n개의 문자열을 더했을 때 가장 큰 수가 나오게 하는 문제이다. 0~9 까지 이기 때문에 주어지는 모든 문자열의 알파벳은 최대 10가지이다. 예를 들어, GCF + ACDEB를 계산한다고 할 때, A = 9, B = 4, C = 8, D = 6, E = 5, F = 3, G = 7로 결정한다면, 두 수의 합은 99437이 되어서 최대가 될 것이다. 처음..

문제 11000번: 강의실 배정 첫 번째 줄에 N이 주어진다. (1 ≤ N ≤ 200,000) 이후 N개의 줄에 Si, Ti가 주어진다. (0 ≤ Si < Ti ≤ 109) www.acmicpc.net N개의 강의 시작 시간과 끝나는 시간이 주어진다. 강의를 모두 다 수용하는 최소한의 강의실의 개수를 구하는 문제이다. 만약 어떤 강의 시간이 끝나는 시간과 시작하는 시간이 같을 때 해당강의실은 동시에 사용이 가능하다. 전형적인 그리디 방법이다. 먼저 강의가 시작하는 시간을 기준으로 오름차순으로 정렬해주었다. class Class implements Comparable{ int start; int end; Class(int start, int end){ this.start = start; this.end =..

문제 9466번: 텀 프로젝트 이번 가을학기에 '문제 해결' 강의를 신청한 학생들은 텀 프로젝트를 수행해야 한다. 프로젝트 팀원 수에는 제한이 없다. 심지어 모든 학생들이 동일한 팀의 팀원인 경우와 같이 한 팀만 있을 www.acmicpc.net N개의 노드의 단방향 그래프 정보가 주어지면 사이클을 포함한 노드를 제외하고 노드가 몇개 있는지 구하는 문제이다. 노드는 항상 한개의 노드만 가리킬 수 있다. 처음 접근은 다음과 같다. N개의 노드마다 dfs를 진행하고, 처음 시작한 노드 번호가 사이클을 이룰 수 있는지 없는지 판단하는 것이다. 따라서 최악의 경우 N^2의 시간 복잡도를 갖게 된다. public class Main { private static int []list; private static i..

문제 11581번: 구호물자 서기 2050년 엄청나게 강력한 폭풍이 인천을 강타했다. 강력한 폭풍의 영향으로 모든 사람은 대피소로 대피하였으며, 많은 도로가 유실되었다. 그나마 남아있는 도로도 모든 표지판과 가로등이 www.acmicpc.net N개의 정점이 주어지면 1번 부터 시작하여 N번까지 가는제 Cycle이 있는지 없는지 판별하는 문제이다. 위에 예시는 N = 3일 경우이다. 처음에는 BFS로 쉽게 구현하였다. boolean[]visit = new boolean[n+1]; Queueq = new LinkedList(); q.add(1); visit[1] = true; boolean check = false; while(!q.isEmpty()){ int curNode = q.peek(); q.rem..

문제 28066번: 타노스는 요세푸스가 밉다 $N$마리의 청설모가 $1$번부터 $N$번까지 순서대로 시계 방향으로 원을 이루면서 앉아있다. 타노스는 손을 튕겨서 순서대로 두 번째 청설모를 제거해 왔는데, 옆 나라의 수학자 요세푸스도 이미 www.acmicpc.net 원형태로 앉아 있는 N 마리의 청설모가 있다. N 마리의 청설모는 각각 1 부터 N까지 번호가 매겨져 있다. 여기서 맨 첫번째 청설모를 제외한 2 ~ K 번째 청설모를 모두 제거한다. 제거한 후 청설모의 수가 2 이상이면 첫번째 청설모의 오른쪽에 있는 청설모가 첫번째 청설모가 된다. 청설모의 수가 K보다 작으면 첫번째 청설모를 제외한 나머지 청설모를 모두 제거한다. 단순한 원형큐 문제였지만, 큐를 사용했을 경우 큐의 맨 앞에 숫자를 삽입하는것..

문제 12100번: 2048 (Easy) 첫째 줄에 보드의 크기 N (1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에는 게임판의 초기 상태가 주어진다. 0은 빈 칸을 나타내며, 이외의 값은 모두 블록을 나타낸다. 블록에 쓰여 있는 수는 2 www.acmicpc.net N * N의 크기의 2차원 배열이 주어진다. 대충 맨 왼쪽 그림처럼 주어지면 여기서 위로 이동시킨것이 2번째 그림이다. 3번째 그림에서 위로 움직인것이 4번째 그림이다. 이렇게 동서남북 아무 방향이나 총 5번 움직일 수 있다. 여기서 만들어지는 가장 큰 수를 구하는 문제이다. 이 문제는 재귀함수를 사용해 브루트포스, 백 트래킹으로 문제를 해결할 수 있었다. 중요한 점은 2차원 배열이 계속 움직이면서 어떻게 저장하고, 임시 배열에 ..

문제 21608번: 상어 초등학교 상어 초등학교에는 교실이 하나 있고, 교실은 N×N 크기의 격자로 나타낼 수 있다. 학교에 다니는 학생의 수는 N2명이다. 오늘은 모든 학생의 자리를 정하는 날이다. 학생은 1번부터 N2번까지 번호 www.acmicpc.net N * N의 크기의 맵에서 학생을 조건에 맞게 배치하는 문제이다. 조건은 다음과 같다. 비어있는 칸 중에서 좋아하는 학생이 인접한 칸에 가장 많은 칸으로 자리를 정한다. 1을 만족하는 칸이 여러 개이면, 인접한 칸 중에서 비어있는 칸이 가장 많은 칸으로 자리를 정한다. 2를 만족하는 칸도 여러 개인 경우에는 행의 번호가 가장 작은 칸으로, 그러한 칸도 여러 개이면 열의 번호가 가장 작은 칸으로 자리를 정한다.  왼쪽 표와 같이 학생의 번호와 그 ..