티스토리 뷰
NYPC Round 2가 어떻게 이뤄질지, 어떤 전략을 사용하는 것이 좋을지 소개해 드리겠습니다.
진행
Round 2는 Round 2-A, Round 2-B 두 개로 나누어집니다. Round 1에서 150점 이상을 받아 통과했으면 이 두 대회에 모두 참가할 수 있고, Round 2-A에서 높은 점수를 받은 N명과, 앞 N명을 제외하고 Round 2-B에서 높은 점수를 받은 N명이 본선에 진출하게 됩니다. 정확한 N은 아직 알려지지 않았지만, 작년에는 총 44명이 본선에 진출하였습니다.
각 Round 2는 3시간 동안 진행되며, 총 4문제가 있습니다. 대회 중 인터넷에 공개되어 있는 코드는 사용할 수 있지만, 대회 시작 이후 나온 자료는 사용할 수 없습니다. 문제별로 여러 부분문제들이 있기 때문에, 이를 잘 이용하는 것이 본선에 있어서 중요합니다.
Round 2-A는 8월 13일 2시~5시, 2-B는 8월 19일 7시~10시에 진행됩니다.
작년 Round 2
NYPC 2023 넥슨 청소년 프로그래밍 챌린지
NEXON YOUTH PROGRAMMING CHALLENGE, 세상을 바꾸는 코딩! 세상을 더 멋지게 바꿀 당신을 만나고 싶습니다.
www.nypc.co.kr
에 들어가면 작년 Round 2 기출문제와 풀이들을 보실 수 있습니다. 저는 작년 Round 2-A에서 1번을 푼 뒤 나머지 부분문제들을 풀어 267로 통과하였고, 재미로 참가한 Round 2-B에서 만점을 맞았습니다.
Round 2 문제들의 난이도가 어땠는지, 어떤 알고리즘들을 사용하였는지 밑에서 간단하게 소개하겠습니다.
2A-1:Gold V 정도, 알고리즘: Sliding Window를 사용하여 모든 구조물이 1개 이하인 동안 오른쪽으로 밀어주고, 안 되기 시작하면 왼쪽으로 밀어줌
2A-2:Platinum III 정도, 알고리즘: dp[i][j]는 i번째 리본과 j번째 리본을 묶었을 때 최대 점수라 했을 때, dp[i+1][j-1]과 더 안쪽을 알면 dp[i][j]를 구할 수 있음, dp2[k]는 i+1~k까지 답이라고 정한 뒤 이를 이용해 dp[i][j]를 구해주면 됨
2A-3:Platinum II 정도, 알고리즘: 로봇의 경로가 한 점에서 교차하면, 그 뒤의 구간을 서로 바꿔서 처리해 주면 되기 때문에 두 로봇이 교차할 일은 없습니다. 각 점마다 어떤 로봇이 처리해야 할지 계산해주면 되는데, 가장 왼쪽에서는 처리해야 할 점을 모두 1번 로봇에게 주면 되고, 가능한 한 최대한 1번 로봇을 오른쪽으로 보낸 뒤, 안 된다면 다음 로봇을 만들면 됩니다.
2A-4:Diamond V 정도, 알고리즘: 시간, r,c를 각각의 차원으로 본다면 3차원 공간으로 나타낼 수 있고, 이는 2차원 세그먼트 트리 스위핑을 사용하면 풀 수 있습니다.
2B-1:Gold IV 정도, 알고리즘: 2i번째 문자+2i-1번째 문자는 항상 합이 1이 되므로, 첫 한 글자와 마지막 한 글자만 체크하면 됩니다. 첫 글자가 1이라면 (0부터 시작하는)글자의 2진수 표현을 K자리 나타낼 때 0이 홀수개 있어야 합니다.
2B-2:Platinum V 정도,알고리즘: A,B에서 이어지는 경로에서 가장 작은 수를 X라 합니다. X->A로 가는 경로, X-B로 가는 경로의 합을 구해주면 됩니다. A,B가 빠르게 작아지려면 제곱수까지 이동한 뒤, 제곱근 연산을 해주면 되므로, 제곱근 연산의 개수에 때라 X를 구할 수 있습니다.
2B-3:Gold I 정도,알고리즘:만약 모든 t가 0이라면 p는 모두 1로 설정해줘야지 가능성이 높아집니다. 만약 1인 t가 있다면, 거기서는 p를 최대한으로 설정해 준 뒤, 0인 t에서는 1인 t를 건드리지 않도록 최대한 설정해둡니다. 그래야 가능성이 가장 높습니다.
2B-4:Platinum III 정도, 알고리즘:1명과만 멘토링이 가능한 멘토나 멘티는 매칭을 해주고 바로 지워줍니다. 그러면 모든 쌍이 매칭이 되면 yes를, 아니면 아무하고도 매칭이 불가능한 멘토, 멘티나, 모두 2명 이상 매칭이 가능해 답이 존재한다면 다른 답이 존재하기 때문에 no를 출력하면 됩니다.
전략
1.문제 순서와 난이도가 반드시 일치하지는 않는다.
다른 문제들과 차이가 컸던 1번 문제를 제외하면, 다른 문제들간의 난이도는 비슷한 경우가 많았고, 사람에 따라서 뒤에 있는 문제를 더 쉽게 푸는 경우도 있었습니다.
2.부분문제는 매우 중요하다.
본선을 가기 위한 커트라인은 200점 이상이 되는데, 이러면 플래티넘 이상의 문제를 하나 풀어야 합니다. 하지만 부분문제를 풀게 된다면, 플래티넘 문제를 풀지 않고도 본선에 갈 수도 있습니다.
3. 인터넷 검색이 큰 도움이 되지는 않을 것이다.
nypc 문제는 알고리즘을 아는 것보다는 알고리즘을 문제에 적용할 수 있는지를 주로 물어보기 때문에, 알고리즘 코드를 가져온다 해서 문제를 풀 때 큰 이득을 받을 수는 없을 것입니다.