왕도를 찾아서

https://www.acmicpc.net/problem/33489  xA_i 를 x와 y에 대해 표현하면... 직접 써보자. A_0 = xA_1 = yA_2 = x - yA_3 = -x + 2yA_4 = 2x - 3yA_5 = -3x + 5yA_6 = 5x - 8y..... 규칙이 보이는지? x와 y의 계수는 피보나치 수열의 숫자들이다.x/y=R이라고 두자.그럼 A_i>0일때마다 1점을 얻으니,0점: x>0 (당연한 소리)1점: y>0 (당연한 소리) x와 y 값에 상관없이 1점은 기본으로 받을 수 있다. 계속해보겠다. 2점: R>1/13점: R4점: R>3/25점: R6점: R>8/57점: R8점: R>21/13.....역시나 규칙이 보인다.R값은 홀수번째 연속된 두 피보나치 수의 비율보다 작아야 하..

https://www.acmicpc.net/problem/33274 일단 n이 짝수인 경우만 생각하자.R1, R2, R3, ....., Rn, C1,C2,....., Cn이라는 총 2n개의 값은 0,1,2,3,.....,2n-1이 되어야 mex값이 최대가 될 수 있다. 문제를 풀 때 가장 먼저 생각했어야 하는 것은 R1~Rn값들의 합은 C1~Cn값들의 합과 같아야 한다는 것이다. n=4인 경우를 예로 들어보겠다.2n-1=7이다.0~7까지 값들을 짝수 홀수로 분류하자. 짝수: 0 2 4 6홀수: 1 3 5 7 이때 짝수를 앞에 있는 것 절반, 홀수를 뒤에 있는 것 절반을 가져와서 한 세트로 묶고, 나머지를 다른 한 세트로 묶으면 각 세트의 수들의 합이 14로 같아진다. 세트1: 0 2 5 7세트2: 1 3..

https://www.acmicpc.net/problem/32715  십자가의 중심이 되는 점을 찾고자 한다.가로줄을 전부 순회하면서 한 점을 중심으로 좌우로 연속으로 2K+1개 칸이 색칠되어 있는 것들을 찾아 십자가 중심의 후보로 넣는다.세로줄도 똑같이 순회하면서 후보를 찾는다.이때 겹치는 것이 십자가의 중심이 된다. 특정 점을 중심으로 가로로도 세로로도 2K+1개 칸이 색칠되어 있는 점을 말하는 거다. #include using namespace std;typedef long long ll;int main(){ ll n,m,k; cin>>n>>m>>k; int a[3100][3100];//색칠 여부를 배열로 저장 ll ans=0; for(ll i=0;i>a[i][j]; ..

https://www.acmicpc.net/problem/31778  포닉스에게는 아끼던 문자열 S가 있다. S는 길이가 N이며 알파벳 대문자 C와 P만으로 이루어져 있는 문자열이다. 문자열 S의 i번째 문자는 S_i이 나타낸다.포닉스는 PPC에 참가하는 팀들을 위해 문자열 S 대회장을 장식하려 한다. 포닉스는 대회 전, S에 다음과 같은 연산을 최대 K번 시행할 수 있다. 1≤i포닉스의 목표는 완성된 문자열 S에 PPC 부분문자열이 가장 많게 하는 것이다. PPC 부분문자열의 개수란, 1≤i포닉스가 만들 수 있는 PPC 부분문자열의 개수의 최댓값을 구하여라. 문제는 두 단계로 나눌 수 있다.1단계는 PPC 부분문자열의 개수가 최대가 되도록 연산을 K번 수행해 문자열 S를 완성시키는 것이다.2단계는 완성..

https://www.acmicpc.net/problem/23032 더보기서프라이즈! 다음과 같은 조건을 만족하는 학생들에게 스테이크를 드려요!1. 임의로 연속된 학번의 학생들을 정해요!2. 임의로 대상 학생들을 두 그룹으로 나눠요! 대신 한 그룹의 학생들은 학번이 인접해야 해요! 그룹에는 최소 한명의 학생이 있어야 해요!3. 두 그룹의 스테이크 무게 합의 차 E를 구해요! E를 계산할 때는 합이 큰 그룹에서 작은 그룹의 합을 빼요!4. 가능한 모든 경우에 대해 계산하여 E가 최솟값인 두 그룹의 학생들에게 스테이크를 드립니다!5. 대신 최솟값이 같은 경우가 여러 가지라면 두 그룹의 스테이크 무게 합이 가장 큰 두 그룹의 학생들에게 스테이크를 드립니다!예를 들면, 1번~6번 학생에 대한 설문 조사 결과가 ..

https://www.acmicpc.net/problem/13018 13018번: 특이한 수열 첫째 줄에 n, k (1 ≤ n ≤ 105, 0 ≤ k ≤ n)가 주어진다. www.acmicpc.net 골드3 난이도의 수학 분류 문제다. 이 문제의 핵심은 바로 임의의 자연수 N에 대해 N과 N+1은 서로소라는 것에 있다. i와 A[i]가 서로소가 아닌 게 k개로 서로소인 게 n-k인 것이다. 이 때 n-k를 p라고 하자. 1은 모든 수랑 서로소이기도 하다. 그러면 숫자를 이런식으로 1씩 밀려 쓰면 1 2 3 4 5 2 3 4 5 1 이러면 모든 i에 대해 A[i]와 i가 서로소가 된다. 1부터 p까지 모든 수에 대해서만 이렇게 밀려 쓰면 된다. 그 뒤 모든 수들은 밀려쓰지 않고 그대로 쓰면 된다. 이를테면..

https://www.acmicpc.net/problem/23325 23325번: 마법천자문 최근最近 만화漫畫 마법천자문魔法千字文을 감명感銘 깊게 읽은 연두然斗는, 모든 수數를 한자漢字로 적기 시작始作했다. 그런데 수업授業을 들으면서 필기筆記 해놓은 내용內容을 복습復習 www.acmicpc.net 전형적인 DP문제다. 요즘 너무 DP만 푸는거 같긴 하다. 계단 문제랑 비슷한 원리다. https://www.acmicpc.net/problem/2579 2579번: 계단 오르기 계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점 www.acmicpc.net 문자열 s의 0번째부터 i..

https://www.acmicpc.net/problem/15011 15011번: Irrational Division Your family has been blessed with chocolate! A huge piece of chocolate has been given to you and your sister to share. However, as you gobbled up the large majority last time, your parents have invented a game to keep things fair (and to keep you occupied www.acmicpc.net 설명은 귀찮으니 그냥 코드로 대체...... 입력이 최대 100이라서 시간복잡도가 아주 널널한 편이다. 내가..

https://www.acmicpc.net/problem/4342 4342번: 유클리드 게임 유클리드 게임은 두 명이서 하는 게임이고, 자연수 2개로 시작한다. 동혁이와 동규는 유클리드 게임을 하려고 한다. 동혁이가 먼저 시작한다. 동혁이는 큰 수를 작은 수의 배수만큼 뺀다. 이때, www.acmicpc.net 골드2 게임이론 문제 치고는 발상이 좀 쉬운 편이다. 내 차례에 숫자가 X X 2*X X 3*X X 등등등 큰 수가 작은 수의 배수라면 무조건 내가 이긴다. 그럼 큰 수가 작은 수의 배수가 아닌 경우라면? 큰 수를 big, 작은 수를 sma라고 부르자. big=sma+1이면 (sma>1) 내 차례에 내가 할 수 있는 건 딱 한가지다. 그리고 상대 차례에 sma 1 이렇게 두 숫자가 주어질 거다. ..

https://www.acmicpc.net/problem/11565 11565번: 바이너리 게임 첫 번째 줄에는 문자열 a, 두 번째 줄에는 문자열 b가 주어진다. 두 문자열은 0과 1로만 이루어져 있으며, 문자열 a와 문자열 b의 길이는 1 이상 1,000 이하이다. www.acmicpc.net 문자열 a에서 1의 개수를 ca라고 하고 문자열 b에서 1의 개수를 cb라고 하자. ca가 홀수인 경우 parity(a)가 1이기 때문에 문자열 끝에 1을 추가할 수 있다. 그러면 parity(a)가 0이 된다. 이러면 문자열 끝에 0을 맘껏 추가할 수 있다. 문자열 앞에서부터 1을 지울 때까지 숫자를 계속 지우면 parity(a)가 1이 된다. 그러면 또 문자열 끝에 1을 추가할 수 있다. 다만, 어떻게 해도..