1. 문제https://www.acmicpc.net/problem/31003문제를 요약하면 인접한 수가 서로소인경우 위치 변경을 할 수 있고, 이러한 시행을 무한히 할 수 있을때, 사전순으로 가장 낮은 수열을 출력해야한다.2. 접근이 문제의 경우 접근이 상당히 어려운 문제이다. 일단 시간복잡도를 생각해보자. 두 숫자의 서로소관계를 파악하기 위해서는 유클리드 호제법을 사용할 수 있다. 시간복잡도 $O(log(N))$ 이러한 시행을 무한히 할 수 있지만, $O(N^2)$ 번의 시행으로 최적의 수열을 만들 수 있다는 것을 어느정도 유추할 수 있다.(직관)그리디하게 문제를 풀 수 없을까 고민해 봤는데 그리디만으로는 힘들어 보인다.수열문제를 가끔식 그래프로 푸는 경우가 있는데, 그래프로도 접근해보자한가지 생각해볼..
단순한 증명 연습하기 좋은 문제가 있어서 포스팅한다 1. 문제 https://www.acmicpc.net/problem/10973 10973번: 이전 순열 첫째 줄에 입력으로 주어진 순열의 이전에 오는 순열을 출력한다. 만약, 사전순으로 가장 처음에 오는 순열인 경우에는 -1을 출력한다. www.acmicpc.net 문제를 요약하면 순열이 주어지는데, 주어진 순열보다 사전순으로 바로 앞선 순열을 출력해야한다. 2. 접근 일단 숫자들이 순열이라는 것에 대해서 중복된 숫자가 없고 $1$부터 $N$까지의 숫자임을 알 수 있다. 순열 사전순으로 제시하는 방법에 대해서 생각해보자. $k$번째 자리수가 낮아진다면 더 $k+1$ 번째 자리수들은 본인들이 가지고 있는 자리수들 중 가장 사전순으로 높은 부분순열조합을 가..
지난 6일에 열린 백준아레나에서 풀지 못한 문제로 업솔빙하려고 한다. 1.문제 https://www.acmicpc.net/problem/28437 28437번: 막대 만들기 첫 줄에 $Q$개의 수를 공백으로 구분해 출력합니다. $i$번째 수는 길이가 $L_i$인 막대를 만드는 방법의 수입니다. 가능한 모든 입력에 대해 답이 $10^9$을 넘지 않음을 증명할 수 있습니다. www.acmicpc.net 문제를 요약하면 주어진 숫자 $ A_1,, A_n $ 으로 가지고 $ L_1,, L_Q $의 각각의 숫자에 대해서 만들 수 있는 경우의 수를 구해야한다. 이때 $ A_1,, A_n $ 의 숫자를 하나 선택해서 곱셈연산을 원하는 만큼 할 수 있다.(곱셈연산이 다르면 다른경우로 분류할수 있다) 예를 들어 $ 1 ..
스터디중 LCA공부중 첼린지 문제를 정하고 공부하면 좋을 것 같아, ICPC문제길래 선택했던 문제인데, 푸는데 걸린 시간이 가장 오래걸린 문제로 거이 4개월이 걸렸다. (심지어 풀이는 LCA를 쓰지 않았다..) 1.문제 https://www.acmicpc.net/problem/26113 26113번: Two Choreographies Your program is to read from standard input. The input starts with a line containing a single integer, $n$ ($4 ≤ n ≤ 100\,000$), where $n$ is the number of static motions two dancers can represent. Each static ..
1. 문제 https://www.acmicpc.net/problem/24553 24553번: 팰린드롬 게임 각 게임에서 상윤이가 이긴다면 0, 승우가 이긴다면 1을 출력한다. www.acmicpc.net $N$개의 돌을 가지고 게임을 한다. 게임의 룰은 1. 상윤이가 롤을 먼저 가져가는 것으로 게임이 시작된다. 2. 자신의 차례에 팰린드롬 수(대칭인 수 ex)1,33,535) $x$를 가져 갈 수 있다. 3. 돌을 가져갈 수 없다면 패배한다. (마지막 돌을 가져가는 사람이 승리한다) 4. 두사람은 모두 최선의 선택을 한다. 2. 접근 문제를 보자마자 돌게임 문제를 풀어 봤다면 dp에 의한 접근 방법을 생각해 볼 수 있다. 게임이론에 대해 처음 접하는 경우 아래 문제를 먼저 푸는 것을 추천한다. https..
1. 문제 https://www.acmicpc.net/problem/28283 28283번: 해킹 네트워크 안에는 $N$개의 컴퓨터가 존재한다. 각 컴퓨터는 $1, 2, \cdots, N$번 컴퓨터로 번호가 붙어있다. 서로 다른 두 컴퓨터 쌍을 연결하는 $M$개의 통신망이 존재한다. $i$번째 통신망은 $S_i$번 컴 www.acmicpc.net $ N $개의 컴퓨터가 주어지고 $ M$개의 통신망의 정보가 주어진다. 두개의 컴퓨터를 연결하는 통신망은 1개 이하이다. %$X$ 개의 컴퓨터를 동시에 해킹하는데 1분마다 해당 컴퓨터의 가중치값인 돈을 얻을수있다. 또한 해킹한 이후 $0.5$ 분정부에서 $Y$개의 컴퓨터에 보안 시스템을 설치한다. 이때 1분 마다 컴퓨터에서 돈을 얻을때 컴퓨터에 보안 시스템이 설..
UCPC 예선에 고전했던 문제로 결국 풀지 못하고 대회가 끝나고 업솔빙하였다. 1. 문제 https://www.acmicpc.net/problem/28305 28305번: 세미나 배정 DEVOCEAN은 SK그룹의 대표 개발자 커뮤니티이자, 내/외부 개발자 간 소통과 성장을 위한 플랫폼이다. DEVOCEAN의 콘텐츠로는 SK 개발자들이 직접 작성한 최신 개발 관련 글과 기술을 공유하고, 테크뉴 www.acmicpc.net 문제를 설명하면 $ N $ (세미나의 개수) 와 $ T $ (세미나기간) 가 주어지고 $ a_1, a_2,,, a_N $ 가 주어 지는데 각각 $ i $번째 세마나가 반드시 진행되야하는 시간이다. 이떄 세미나가 가장 많은 날의 세미나 수의 최솟값을 구해야한다. 예를 들어 위와 같이 inp..
