1. 문제https://www.acmicpc.net/problem/31003문제를 요약하면 인접한 수가 서로소인경우 위치 변경을 할 수 있고, 이러한 시행을 무한히 할 수 있을때, 사전순으로 가장 낮은 수열을 출력해야한다.2. 접근이 문제의 경우 접근이 상당히 어려운 문제이다. 일단 시간복잡도를 생각해보자. 두 숫자의 서로소관계를 파악하기 위해서는 유클리드 호제법을 사용할 수 있다. 시간복잡도 O(log(N)) 이러한 시행을 무한히 할 수 있지만, O(N2) 번의 시행으로 최적의 수열을 만들 수 있다는 것을 어느정도 유추할 수 있다.(직관)그리디하게 문제를 풀 수 없을까 고민해 봤는데 그리디만으로는 힘들어 보인다.수열문제를 가끔식 그래프로 푸는 경우가 있는데, 그래프로도 접근해보자한가지 생각해볼..
단순한 증명 연습하기 좋은 문제가 있어서 포스팅한다 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번째 수는 길이가 Li인 막대를 만드는 방법의 수입니다. 가능한 모든 입력에 대해 답이 109을 넘지 않음을 증명할 수 있습니다. www.acmicpc.net 문제를 요약하면 주어진 숫자 A1,,An 으로 가지고 L1,,LQ의 각각의 숫자에 대해서 만들 수 있는 경우의 수를 구해야한다. 이때 A1,,An 의 숫자를 하나 선택해서 곱셈연산을 원하는 만큼 할 수 있다.(곱셈연산이 다르면 다른경우로 분류할수 있다) 예를 들어 $ 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≤100000), 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,⋯,N번 컴퓨터로 번호가 붙어있다. 서로 다른 두 컴퓨터 쌍을 연결하는 M개의 통신망이 존재한다. i번째 통신망은 Si번 컴 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 (세미나기간) 가 주어지고 a1,a2,,,aN 가 주어 지는데 각각 i번째 세마나가 반드시 진행되야하는 시간이다. 이떄 세미나가 가장 많은 날의 세미나 수의 최솟값을 구해야한다. 예를 들어 위와 같이 inp..
