티스토리 뷰
Round 1에 대하여
NYPC는 Round 1, 2-A, 2-B, 본선 4개의 라운드로 나누어지는데, 이 중 가장 먼저 보고 가장 난이도가 쉬운 대회가 Round 1입니다. Round 1은 일반적 알고리즘 대회와 다른 여러 특징들이 있는데,
1.대회 시간이 몇 시간이 아닌 5일이다.
2.다음 라운드 진출 커트라인이 절대평가로 정해진다.
3.대회 도중에 책이나 대회 시작 전에 올린 블로그 등을 참고할 수 있다.
4.코딩이 필요없고 손이나 시뮬레이터 등으로 풀 수 있는 문제가 나온다.
이렇게 4가지 정도가 대표적인 특징이라 할 수 있습니다.
Round 1의 난이도
Round 1은 프로그래밍을 잘하지 못하는 사람도 참가할 수 있는 만큼 쉬운 문제들이 주로 출제됩니다. 작년 대회의 본선 커트라인은 250점인데, 250점을 넘기 위해서는 브론즈 후반~실버 초반 사이의 문제를 풀고, 시뮬레이터 문제를 손으로 조금 풀면 되었습니다. Round 1의 중반부~후반부에 있는 문제들은 Round 1 특별상을 가리기 위한 문제와, 다음 라운드 참가와 딱히 상관이 없고 푸는 재미를 위한 문제로 구성이 되어있었던 것 같습니다.
Round 1 전략
Round 1은 쉬운 절대평가 대회이고, 충분한 시간이 주어지는 만큼 전략은 딱히 필요 없습니다. 하지만 뒤에 있는 어려운 문제들에서 더 쉬운 상황인 부분문제들을 풀면, 시뮬레이터 문제나 첫 문제를 풀지 못했을 때 도움이 될 수도 있습니다.
Round 1 풀이
1.인류의 적 모기 퇴치
예상 티어:Bronze 1
문제 요약:2차원 배열이 하나 있는데, 어떤 점과 그 점에서 상하좌우로 최대 M칸 이동한 곳(체스의 룩이 한 번에 이동할 수 있는 곳 중 거리가 M 이하인 곳)에서의 배열의 값들을 합한 것의 최댓값과, 어떤 점과 그 점에서 대각선 4방향으로 최대 M칸 이동한 곳(체스의 비숍이 한 번에 이동할 수 있는 곳 중 거리가 M 이하인 곳)에서의 배열의 값들을 합한 것의 최댓값 중 더 큰 것을 구하라
풀이: 2차원 배열의 크기가 최대 50*50이라 나와 있으므로, 어떤 점은 최대 2500개이고, 상하좌우를 체크하는 것과 대각선을 체크하는 것 2가지가 있으므로 5000개를 체크하면 됩니다. 어떤 점들은 2중 for문으로 순회할 수 있고, 상하좌우와 대각선 내에서의 합을 더하는 것은 이 안에 for문을 하나 더 넣어 주면 됩니다. 배열의 인덱스를 벗어나는 곳을 접근하지 않도록 주의해 줍시다. 저는 모든 좌표에 M의 최대인 50을 더하는 방법으로 해결했습니다.
여담:nypc 공식 풀이를 보면, 두 개의 점을 고르고, 중복해서 합해지는 점은 한 번만 더한다는 내용이 나와 있는데, 이러면 구현이 복잡해지거나, 코드의 실행 시간이 길어져 python 등의 언어에서 돌아가지 않는 등의 이유로 지금의 문제로 바뀐 것으로 보입니다.
2.카트라이더 보드게임
예상 티어:N과 X가 입력으로 주어지는 일반적인 문제라 한다면 Silver 1
위에 문제에서 만점을 맞았으면, 이 문제의 부분문제 중 3번까지 풀면 다음 라운드로 진출할 수 있습니다.
문제 요약:보드게임 보드가 주어지고, 원하는 눈이 나오는 주사위가 있다. 보드의 어떤 칸에 도착하면 몇 개의 루찌를 받을 수 있다. 이 상황에서 주사위를 N번 굴려 M번 칸에 갈 때, 최대 루찌의 수와 경로를 출력하라
풀이:3번까지는 손으로 풀고 시행착오를 해보면 쉽게 할 수 있습니다. 하지만 10번 문제는 1000번의 주사위 굴리기를 실수 없이 해야 하므로, 손으로 하기는 불가능합니다. 따라서 컴퓨터를 사용해야 하는데, 다이나믹 프로그래밍을 이용하면 됩니다.
dp[i][j]는 i번 주사위를 던져 j번째 칸에 있을 때, 얻을 수 있는 최대 루피 수입니다. 상태 전이는 dp[i+1][j]=max(dp[i][k]+j번 칸 루찌 수)이고 k에서 j로 갈 수 있 수 있어야 합니다. k에서 j로 갈수 있는지 계산하기 위해 dp2[k][j]=k에서 j로 가기 위해 필요한 최소 눈 수를 만들어주고, bfs를 사용해 최단 거리를 구해줍니다. dp2[k][j]<=6이고 k!=j여야 합니다.
이러면 답을 구할 수는 있지만, 어떻게 가는지 찾기는 불가능합니다. 따라서 dp3[i][j]는 dp[i][j]의 상황에서 직전에 있었어야 하는 칸과 나온 주사위 눈 수라 하고, 이를 dp[i][j]와 같이 관리하면 풀 수 있습니다.
3.뒤집기
예상 티어:Gold 4
문제 요약: 배열의 어떤 연속한 구간을 뒤집은 뒤 최대 부분합을 구하는 문제
풀이:배열에 연속한 구간은 O(N^2)개 있으므로, 이를 다 뒤집어볼 수는 없습니다. 하지만 배열의 어떤 연속한 구간을 뒤집은 뒤 부분합은 원래 배열에서 겹치지 않는 2개의 부분합의 합으로 표현할 수 있습니다.
dp[i][0]=i번째 원소롤 보고 있고, 첫 번째 부분합에 더하는 중
dp[i][1]=i번째 원소롤 보고 있고, 첫 번째 부분합과 두 번째 부분합 사이
dp[i][2]=i번째 원소롤 보고 있고, 두 번째 부분합에 더하는 중
이렇게 dp를 세우고, dp[i][0]은 이번에 더하기 시작한 경우 or 저번에서 이번으로 이어지는 경우
dp[i][1]은 이번에 끝난 경우 or 저번에 끝났고 아직 시작 안한 경우
dp[i][2]=이번에 더하기 시작한 경우 or 저번에서 이번으로 이어지는 경우와 같이 전이하면
답은 max(dp[i][0],dp[i][2])가 됩니다. 시간 복잡도는 O(N)입니다.
4.카트 제작
예상 티어:Gold 2
문제 요약:a,b,c,d,e 5가지의 파츠가 있고, 각 종류마다 다양한 파츠를 가지고 있다(최대 600개). 각 파츠는 기본 성능과 시너지가 있는데, 시너지는 a-b,a-c,a-d,a-e,b-c,d-e 사이에서만 생긴다. 성능이 S에 가장 가까운 조합을 만들어라.
풀이:
각 파츠 종류별로 120개의 파츠가 있기 때문에, 모든 경우의 수를 볼 수는 없습니다.일단 a를 고정해 봅시다. 이러면 a와 다른 파츠들 간의 시너지는 b,c,d,e의 기본 성능이 올라가는 것으로 볼 수 있습니다. 이러면 가능한 모든 b-c의 쌍과 d-e의 쌍을 체크하여 성능의 합을 계산한 다음, 이 두 배열을 정렬한 뒤 b-c의 쌍에 대해 적절한 d-e의 쌍을 이분 탐색으로 찾아주면 됩니다. 시간 복잡도는 O(N^3logN)이지만, 상수가 작기 때문에 잘 돌아갑니다.
5.달팽이
예상 티어: Gold 2
문제 요약:
위와 같은 패턴의 N*N 격자의 두 점의 번호가 주어진다. 두 점으로 만들어지는 직사각형이 정사각형인지 계산하라.
풀이:N*N 격자에서 바깥 테두리에 있는 점은 4(N-1)개이고, 1~4(N-1)까지 번호가 붙어 있습니다. 그리고 그 내부는 N-2*N-2 격자의 답에 모두 4(N-1)을 더한 것과 같습니다. 따라서 어떤 점이 몇 번째 바깥 테두리에 있는지는 이분 탐색을 통해 O(log N) 정도의 시간에 계산할 수 있습니다. (N=1인 경우 주의해야 합니다.) 몇 번째 테두리인지를 알면 테두리를 4등분한 뒤 좌표에 대한 케이스를 나눌 수 있습니다. 각각의 x,y 좌표가 나오면 x좌표의 차의 절댓값=y좌표의 차의 절댓값 인지 체크하면 됩니다.
6.바텐더
예상 티어: Gold 1
문제 요약:배열 A가 있고, 매 턴 1,2,4,1,2,4,....의 규칙에 따라 배열의 어떤 원소를 늘리거나, 그대로 둘 수 있습니다. A의 모든 원소를 같게 하는 최소 턴 수를 구하라.
풀이:같아진 원소의 값을 t라 할 때, t는 A의 최댓값+4 이상이 될 수 없습니다. t가 A의 최댓값+4 이상이라면 모든 A의 원소에서 4를 덜 더해서 같은 결과를 낼 수 있고, 4를 덜 더하는 것은 항상 가능합니다(1111,112,22,4를 뺄 수 있습니다)
따라서 t의 값을 고정하면서 풀 수 있고, t의 값을 고정했을 때 A의 원소마다 더해야 하는 값이 나옵니다.
이제 이분탐색을 해주는데, 총 x턴을 쓸 때 사용 가능한 1,2,4의 값을 구하고, 4를 더할 수 있는 곳에 아무렇게, 그 다음 2,1 순서대로 하면 최적의 결과가 나옵니다.
7.MBTI 궁합을 이용한 조 구성
예상 티어: Platinum 5
문제 요약:N개의 0~15 사이의 수가 주어지고, 이를 두 개씩 묶어야 한다. 묶은 수의 어떤 비트들이 서로 다르면, 각 비트 위치마다 다른 점수가 더해진다. 점수가 최소화되도록 수를 묶어라
풀이:같은 수가 2개 이상 있으면, 그 수들끼리 묶는 것이 최선이라는 것은 쉽게 알 수 있다. 이러면 최대 16개의 수들이 남게 되는데, 수가 충분히 작아졌기 때문에 백트래킹 등으로 묶으면 해결할 수 있다.