본문 바로가기

Algorithm

 (20)
Codeforces Round 908 (Div. 2) 풀이 https://codeforces.com/contest/1894 Dashboard - Codeforces Round 908 (Div. 2) - Codeforces codeforces.com A. Secret Sport Problem https://codeforces.com/contest/1894/problem/A Problem - A - Codeforces codeforces.com 두 플레이어 A, B가 참여하는 게임이 있으며, 이 게임은 두 양의 정수 X, Y로 표현할 수 있다. 이 게임은 여러 세트로 이루어져 있으며, 각 세트는 여러 판으로 이루어져 있다. 각 판에서는 A와 B 중 정확히 한 사람만이 이길 수 있으며, 하나의 세트는 플레이어 한 명이 X 판을 이기는 즉시 종료 되며, 해당 플레이어가..
Codeforces Round 864 (Div. 2) 풀이 A. Li Hua and Maze Problem A. Li Hua and Maze Problem - A - Codeforces codeforces.com n*m 크기의 직사각형 미로가 있다. (r, c)를 위에서부터 r번째 행, 왼쪽부터 c번째 열이라고 하자. 두 칸이 변을 공유하고 있다면 그 두 칸은 인접하다고 부른다. 길은 인접한 빈칸들의 수열이다. 각 칸들은 초기에 모두 비어 있다. Li Hua는 ($(x_1, y_1)$과 $(x_2, y_2)$를 제외하고) 몇 개의 칸들을 고를 수 있다. 그리고 그 칸들에 장애물을 설치한다. 그는 $(x_1, y_1)$에서 $(x_2, y_2)$까지 가는 길이 없도록 하기 위해 설치해야 하는 장애물의 최소 개수를 알고 싶어 한다. 당신이 Li Hua라고 가정하고,..
백준 8907번 네온 사인 풀이 문제 Boj. 8907 - 네온 사인 8907번: 네온 사인 첫째 줄에는 테스트 케이스의 수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 꼭짓점의 개수 N(3 ≤ N ≤ 1,000)이 주어진다. 다음 N-1개의 각 야광 튜브의 색이 주어진다. 이 줄의 i번째 줄에는 꼭 www.acmicpc.net 풀이 나는 문제를 풀 때 정해가 바로 떠오르지 않는다면 시간을 고려하지 않고 답을 도출해낼 수 있는 풀이를 생각한다. 그 후, 가장 안쪽에 있는 반복문부터 시간을 줄이는 방법을 생각해 정해를 도출해낸다. $O(N^3)$ 풀이 아마 $O(N^3)$ 풀이는 다들 쉽게 떠올렸을 것이다. 삼각형은 3개의 꼭짓점으로 이루어져 있기 때문에 3중 반복문을 이용하여 가능한 모든 경우의 삼각형을 찾을 수 있다. 이렇게 선택..
Codeforces Round #829 (Div. 2) A. Technical Support Problem A. Technical Support Problem - A - Codeforces codeforces.com 당신은 큰 회사의 기술 지원의 품질 관리 부서에서 일하고 있다. 당신의 일은 모든 고객 문제가 해결되었는지 확인하는 것이다. 오늘 당신은 고객과 기술 지원 관리자 사이의 대화 내용을 확인해야 한다. 업무 규칙에 따라, 각 고객의 메시지는 지원 관리자의 대답에 해당하는 하나 혹은 여러 개의 메시지가 따라 나와야 한다. 그러나 가끔 고객들은 너무 빨리 질문을 해서 이전 질문들에 대한 몇몇 관리자의 답변들은 고객들이 요청한 새로운 질문 뒤에 나타나기도 한다. 보안 정책에 때문에, 메시지의 전체 내용은 당신에게 보여주지 않고, 오로지 메시지 타입과 순서..
Educational Codeforces Round 136 (Rated for Div. 2) - D D. Reset K Edges Problem D. Reset K Edges Problem - 1739D - Codeforces codeforces.com n개의 정점으로 이루어진 루트가 있는 트리가 주어진다. 정점들은 1부터 n까지 번호가 붙어 있으며, 루트는 1번 정점이다. 당신은 다음의 작업을 최대 k번 수행할 수 있다: 정점 v가 정점 u의 부모인 간선 (v, u)를 선택한다; 간선 (v, u)를 지운다; 간선 (1, u)를 추가한다 (즉, 정점 u와 그 서브트리를 루트의 자신으로 만든다). 트리의 높이는 정점들의 깊이 중 최댓값이며, 정점의 깊이는 루트부터 해당 정점까지 가는 경로 상의 간선 개수이다. 예를 들어, 정점 1은 루트이기 때문에 깊이가 0이고, 그 자식들은 깊이가 1이다. 만들 수 있..
Educational Codeforces Round 136 (Rated for Div. 2) A. Immobile Knight Problem A. Immobile Knight Problem - A - Codeforces codeforces.com $n \times m$ 크기의 체스판이 있다. 가로는 1부터 n까지, 세로는 1부터 m까지 번호가 붙어 있다. 만약 체스판 위의 어떠한 칸에서 나이트가 다른 칸으로 이동할 수 없다면 그 칸을 독립된 칸이라고 부르자. 체스에서 나이트는 한 방향으로 두 칸 이동한 뒤, 이동한 방향과 수직한 방향으로 한 칸 이동한다. 체스판에서 독립된 칸을 찾아라. 마약 그러한 칸이 없다면, 아무 칸이나 출력하여라. Input 첫째 줄에는 테스트 케이스의 수를 나타내는 하나의 정수 t($1 \leq t \leq 64$)가 주어진다. 각 테스트케이스는 하나의 줄로 이루어졌으며..
Codeforces Global Round 21 A. NIT orz! Problem A. NIT orz! Problem - A - Codeforces codeforces.com 번호가 1부터 부여된 n개의 정수로 이루어진 배열 a와 하나의 정수 z가 주어진다. 너는 다음 작업을 몇 번이든(0번도 가능) 할 수 있다: $1 \le i \le n$인 양의 정수 i를 고른다. 동시에 $a_i$를 ($a_i \, or \, z$)로, $z$를 ($a_i \, and \, z$)로 바꾼다. 다시 말해 현재 $a_i$와 $z$의 값이 $x$, $y$라고 하면, $a_i$는 ($x \, or \, y$)로, z는 ($x \, and \, y$)로 바꾼다. 여기서 or와 and는 비트연산을 의미한다. 여러(0번도 가능) 작업을 수행한 후 배열 a의 최댓값으로 가능한..
Educational Codeforces Round 127 (Rated for Div. 2) - E 개인적으로 풀이 생각 과정과 AC를 받았을 때 희열을 느낀 문제 중 하나입니다. E. Preorder Problem E. Preorder Problem - E - Codeforces codeforces.com $2^n - 1$개의 정점을 가진 루트 트리가 주어진다. 각 정점은 0개 혹은 2개의 자식을 같는다. 트리의 모든 말단은 루트로부터 같은 길이를 가지며, 모든 중간 정점은 하나의 왼쪽 자식과 하나의 오른쪽 자식을 같는다. 즉, 완전 이진트리가 주어진다. 트리의 정점은 다음의 순서로 번호가 붙는다: 루트의 인덱스는 1이다 어떤 정점의 인덱스가 x라면, 그 정점의 왼쪽 자식의 인덱스는 2x, 오른쪽 자식의 인덱스는 2x+1이다. 트리의 모든 정점에는 A와 B 중 하나의 알파벳이 쓰여 있다. 정점 x의 ..

티스토리툴바