복습노트 복습노트

문제 21318번: 피아노 체조 피아노를 사랑하는 시은이는 매일 아침 피아노 체조를 한다. 시은이는 N개의 악보를 가지고 있으며, 1번부터 N번까지의 번호로 부른다. 각 악보는 1 이상 109 이하의 정수로 표현되는 난이도를 www.acmicpc.net 피아노 악보 n개가 주어지고 각 n개의 악보마다 난이도가 주어집니다. 만약 i번째 악보가 i+1악보의 난이도보다 높다면 실수 합니다. 구간 x~y가 주어진다면 실수하는 횟수를 구하는 문제입니다. prefix sum을 이용하여 해결하였습니다. psum[i] = 1부터 i번째 까지 실수하는 횟수로 정의하였습니다. 구간 [x, y] = psum[y] - psum[x]로 구할 수 있습니다. 전체 코드입니다. HTML 삽입 미리보기할 수 없는 소스

구간에 대한 여러 정보를 효율적으로 관리하는 자료구조 ex) prefix sum(특정한 구간의 합) 예시문제 백준 2042 (구간 합 구하기) c++ 문제 2042번: 구간 합 구하기 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)과 M(1 ≤ M ≤ 10,000), K(1 ≤ K ≤ 10,000) 가 주어진다. M은 수의 변경이 일어나는 횟수이고, K는 구간의 합을 구하는 횟수이다. 그.. riveroilstone.tistory.com

문제 2042번: 구간 합 구하기 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)과 M(1 ≤ M ≤ 10,000), K(1 ≤ K ≤ 10,000) 가 주어진다. M은 수의 변경이 일어나는 횟수이고, K는 구간의 합을 구하는 횟수이다. 그리고 둘째 줄부터 N+1번째 줄 www.acmicpc.net n개의 숫자를 차례대로 입력받고 m번의 수 변경이 일어나고 k번의 구간의 합을 구하는 문제입니다. a가 1이면 b번째 수 위치를 c로 바꾸고 a가 2이면 b부터 c 구간의 합을 구하면 됩니다. 따라서 총 m+k번의 쿼리가 진행 됩니다. 단순히 prefix sum으로 해결하기에는 수를 계속 해서 바꿔주는 과정이 있기 때문에 더 효율적인 시/공간 복잡도로 이루어진 자료구조가 필요합니다. 따라서 Segm..

문제 16884번: 나이트 게임 첫째 줄에 테스트 케이스의 개수 T(1 ≤ T ≤ 100)가 주어진다. 둘째 줄부터 T개의 줄에 테스트 케이스가 한 줄에 하나씩 주어지며, 체스판의 크기 N(1 ≤ N ≤ 10,000)으로 이루어져 있다. www.acmicpc.net n * n 체스판에서 A와 B가 체스를 두는데 서로 체스 말을 '나이트'로 고정하고 번갈아가면서 나이트가 공격할 수 없는 공간에다가 나이트를 둡니다. 선공은 A가 먼저하고 승리하는 사람을 출력해주면 되는 문제입니다. 손으로 그림을 그려가면서 규칙성을 찾아보려 했지만 찾을 수 없었고 외부 블로그에서 영감을 얻어 해결하였습니다. 먼저 후공인 B가 이기는 최선의 방법을 구하는 것입니다. 결론 부터 얘기하면 B는 A가 두는 나이트의 점대칭 인곳에 체..

문제 17965번: Absolute Game Alice and Bob are playing a game. Alice has an array a of n integers, Bob has an array b of n integers. In each turn, a player removes one element of his array. Players take turns alternately. Alice goes first. The game ends when both arrays contain exactl www.acmicpc.net A와 B에게 길이가 같은 배열이 주어지면 A와 B는 서로 한번씩 배열의 숫자 1개를 제거할 수 있습니다. 가지고 있는 배열 중 마지막 원소 1개를 제외하고는 모두 제거 할 수 있는..

스프라그-그런디 정리 애드혹/그리디 1) 같은 행동조건 2) 승리 조건이 동일 (상대가 승리하면 내가 패배, 상대가 패배하면 내가 승리) 1) dp로 푸는 유형(시간복잡도와 공간복잡도를 고려하지 않는다면 모든 문제에 적용 가능) dp[x] : x라는 상태에서 선공이 이긴다면 true, 아니라면 false x에서 갈 수 있는 행동집합들을 모두 살펴보면서, 선공이 지는 상태(즉 상대를 패배하게 만드는 상태) 로 만들 수 있다면 x는 선공이 이길 수 있는 상태인 것이다. 예시 문제 백준 9655 (돌 게임) c++ 문제 9655번: 돌 게임 상근이가 게임을 이기면 SK를, 창영이가 게임을 이기면 CY을 출력한다. www.acmicpc.net 상근이와 창영이가 주어진 n개의 돌을 서로 번갈아 돌아가면 1개 또는..

문제 Problem - 1600E - Codeforces codeforces.com 배열이 주어지면 Alice와 Bob이 서로 한번씩 돌아가면서 배열의 양쪽 끝의 숫자를 뺄 수 있습니다. 두명이 뺀 숫자들은 항상 증가 수열을 이뤄야하며 자신의 차례에서 증가수열을 이룰 수 없을 때 그 사람은 패배 입니다. 선공은 항상 Alice가 먼저이고 두 사람중 승리하는 사람을 출력하는 문제 입니다. 예를들어 배열에 3, 8, 10, 5, 7, 6 이 있다고 하면 Alice는 양쪽 끝인 3과 6을 선택할 수 있습니다. 만약 6을 선택하면 두사람은 항상 오른쪽의 수만 빼야 합니다. 3은 6보다 작으므로 증가수열을 이룰 수 없기 때문입니다 그럼 Bob이 7을 뽑으면 Alice는 더이상 뽑을 숫자가 없어지므로 패배하게 됩니..

문제 12107번: 약수 지우기 게임 1 N=4인 경우, A는 처음에 4,2,1을 지운다. 칠판에 남은 수는 3으로, B는 3을 지울 수밖에 없어 패배한다. www.acmicpc.net n이 주어지면 칠판에 1부터 n까지의 자연수를 쓰고 A와 B가 돌아가면서 칠판에 적혀진 자연수를 포함한 약수를 지우는 게임 입니다. 마지막 숫자를 지우는 사람이 지게 됩니다. 선공은 A부터 합니다. 1은 모든수의 약수입니다. 따라서 1은 항상 지워집니다. 만약 내가 이기는 판이면 그대로 게임을 진행하고 지는 판이면 맨 처음에 1 한개만 지웠다고 가정하고 상대판에게 턴을 넘기면 됩니다. 예를 들어 주어진 숫자가 5이면 1 2 3 4 5 먼저 A가 4(1, 2, 4)를 지우게 되면 3 5 다음 B가 3과 5 둘중 아무거나 지..