PS/BOJ

https://www.acmicpc.net/problem/12902시간 제한메모리 제한2초512MB문제Alice와 Bob은 두 명이 할 수 있는 게임을 하나 만들었다. 규칙은 다음과 같다.n개의 서로 다른 자연수로 이루어진 집합을 하나 갖고 시작한다.두 명은 번갈아서 차례를 가지며, 각자의 차례에 다음과 같은 동작을 수행한다: 집합 내에서 서로 다른 두 자연수 x와 y를 고른다. 단, |x-y|가 집합 내에 존재해서는 안 된다. 이렇게 x와 y를 고른 이후, 그것을 고른 사람이 |x-y|를 집합 내에 넣는 것으로 그 사람의 차례가 종료된다.더 이상 고를 수 있는 (x,y)가 없는 사람이 패배한다.두 사람이 모두 최적의 전략으로 플레이할 때, 처음에 주어진 n개의 자연수에 대해 누가 승리하게 될지 출력하시..

https://www.acmicpc.net/problem/15311시간 제한메모리 제한1초512MB문제약장수 강욱이는 오늘도 약을 판다. 짬에서 나오는 Vibe로 화려한 언변을 구사하는 강욱이는 최고의 약장수이다. 하지만 이런 그에게도 고민거리가 하나 있으니... 동규라는 단골 손님이 있는데, 그는 매일 약을 1알에서 100만알 사이의 랜덤한 자연수 개수만큼 원했다. 주문을 받은 강욱이는 약 상자에서 한 알씩 약을 세서 꺼내주곤 했는데, 그것이 답답했던 동규는 강욱이에게 매번 화를 냈던 것이다. 이러다 동규가 자기를 때리지 않을까 무서웠던 강욱이는 동규가 원하는 만큼의 약을 빨리 건네주기 위한 방법을 고민하기 시작했다. 그는 곧 소싯적에 공부했던 Algorithm을 이용해 다음과 같은 방법을 생각해 냈다..

https://www.acmicpc.net/problem/25547시간 제한메모리 제한1초1024MB문제두 양의 정수 A, B가 주어질 때, 다음과 같은 조건을 만족하는 양의 정수 C의 개수를 구하여라. GCD(A, B) = GCD(A, C), LCM(A, B) = LCM(B, C) GCD(A, B)는 A와 B의 최대공약수를, LCM(A, B)는 A와 B의 최소공배수를 의미한다. 입력양의 정수 A, B가 주어진다. (1 ≤ A, B ≤ 1,000,000,000) 출력조건을 만족하는 양의 정수 C의 개수를 출력한다. 풀이매우 난해한 문제 같지만 주어진 식을 정리해보면 매우 간단한 문제입니다. 먼저 최대공약수 식을 정리해봅시다. GCD(A, B)를 G라고 했을 때, A = a*G, B = b*G로 표현할 수..

https://www.acmicpc.net/problem/16877 시간 제한메모리 제한0.5초512MB문제koosaga와 cubelover가 "핌버"를 하고 있다. 핌버는 님 게임에 규칙을 추가한 게임이다. 핌버는 돌을 차곡 차곡 위로 쌓아올린 돌 더미 k개를 이용한다. 각각의 돌 더미에는 한 개 이상의 돌이 있다. 두 사람은 서로 턴을 번갈아가면서 핌버를 진행한다. 각 사람의 턴이 되면, 돌 더미 하나를 선택해 돌을 제거한다. 제거한 돌의 개수는 피보나치 수여야 한다. 전체 돌 더미에서 마지막 돌을 제거하는 사람이 게임을 이기게 된다.  게임은 koosaga가 먼저 시작한다. 두 사람이 최적의 방법으로 게임을 진행했을 때, 이기는 사람을 출력한다. 입력첫째 줄에 돌 더미의 개수 N (1 ≤ N ≤ 1..

https://www.acmicpc.net/problem/17384시간 제한메모리 제한1초(추가 시간 없음)1024MB문제수빈이는 예전부터 UCPC의 대회 형식이 ICPC와 같다는 것이 마음에 들지 않았다. 그래서 전대프연의 회장이 되자마자 UCPC를 ICPC와 차별화된 토너먼트 방식의 대회로 바꾸겠다고 선언했다.수빈이가 바꾼 새로운 UCPC의 진행 방식은 다음과 같다.참가한 팀의 수보다 크거나 같은 가장 작은 2의 거듭제곱 꼴의 수를 찾고, 그 수만큼 빈 슬롯을 일렬로 나열한다.참가한 팀들을 슬롯들에 적절히 배정한다. 이때 두 개 이상의 팀을 같은 슬롯에 배정할 수는 없다.슬롯들을 앞에서부터 두 개씩 짝짓는다. 만약 짝지어진 두 슬롯 모두 팀에 배정되어 있다면 두 팀이 경기를 치르고, 패배한 팀의 슬롯..

https://www.acmicpc.net/problem/25589시간 제한메모리 제한1초1024MB문제N*N 크기의 격자 위에 칸마다 코인이 놓여있다.푸앙이는 격자 위에 한 변의 길이가 1 이상 N이하인 정사각형 그물을 만들어 그 안의 코인을 얻을 수 있다. 하지만 그물이 포함하는 칸 개수의 제곱에 해당하는 코인을 지불해야 한다.그물은 반드시 N*N크기의 격자 안에 완전히 포함 되어야 하고, 한 번 그물을 친 칸에는 다시 그물을 칠 수 없다.푸앙이가 정확히 두 번의 그물을 쳐서 얻을 수 있는 코인의 최대 개수를 구하시오. 입력첫 번째 줄에 정수 N(2 ≤ N ≤ 400)이 주어진다.두 번째 줄부터 N개의 줄에는 칸에 놓여 있는 코인의 수가 1행부터 차례대로 주어진다. 칸에 놓여 있는 코인의 수는 10^..

시간 제한메모리 제한2초1024MB문제정점이 N개가 있는 트리가 있고 각 정점들은 1부터 N까지 번호가 매겨있다. 해당 트리로부터 (N-2)개의 양의 정수로 이루어진 수열 하나를 다음과 같은 과정을 통해서 만들 것이다.차수가 1인 정점들 중에서 번호가 가장 큰 정점을 하나 고른다. 해당 정점을 x라고 부르자.정점 x와 인접한 정점의 번호를 수열에 넣는다.정점 x와 인접한 간선들을 해당 트리에서 지운다.1번부터 3번까지의 과정을 총 (N - 2)번 진행한다.수열 {a1, ... , aN-2}가 주어졌을 때, 위의 과정을 통해서 이 수열을 만들 수 있는 트리를 구하여라.입력다음과 같이 입력이 주어진다.Na1 ··· aN-2 출력해당 트리가 존재한다면 간선 (N-1) 개를 다음 규칙에 만족하게 출력한다.각 간..

https://www.acmicpc.net/problem/8895시간 제한메모리 제한1초256MB문제높이가 1, 2, ..., n인 막대 n개가 일렬로 배치되어 있다. 막대를 왼쪽이나 오른쪽에서 보면, 큰 막대가 뒤에있는 작은 막대를 가리게 된다. 아래와 같이 4개의 막대로 이루어진 두 배치를 살펴보자.위의 두 배치는 모두 왼쪽에서 봤을 때 막대가 한 개 보이고, 오른쪽에서 봤을 때는 막대가 두 개 보인다. 막대의 개수 n과 왼쪽에서 봤을 때 보이는 막대의 개수 l, 오른쪽에서 봤을 때 보이는 막대의 개수 r이 주어진다. 이때, 이러한 결과를 만드는 배치의 개수를 구하는 프로그램을 작성하시오. 입력첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, n, l, r이..