2022 홍익대학교 HI-ARC 프로그래밍 경진대회 Open Contest

2022 홍익대학교 HI-ARC 프로그래밍 경진대회 Open Contest

A - HI-ARC

단순 구현

00:02 AC

 

B - 나뭇잎 학회

2 이상의 N에 대하여 답은 (N * N + 1) / 2 이다.

증명 없이 감으로 제출하였다.

00:06 AC

 

C - K-Queen

N-Queen 문제와 유사하게 처리하면 된다.

00:13 AC

 

D - Codepowers

무작정 Merge Sort Tree 박았다.

00:20 AC

정해는 누적 합이다.

 

F - 험난한 등굣길

정해에 비하여 굉장히 복잡하게 풀었다.

다들 굉장히 빨리 풀길래 감탄하였는데 내가 꼬아서 풀었다.

 

나의 풀이는 다음과 같다.

우선 격자를 45도 회전시킨다.

이렇게 하면 정체 구역을 사각형 형태로 관리할 수 있다.

정체 구역은 2차원 누적 합으로 O(NM)에 구할 수 있다.

마지막으로 bfs 돌리면 된다.

 

격자 회전시키고 변경된 좌표값 계산하는 데 시간을 다 썼다.

01:05 WA

격자를 45도 회전시키면 실제로 존재하지 않는 정점들이 생길 수 있다.

bfs 과정에서 이러한 정점들은 제외시켜야 한다.

01:12 AC

 

정해의 핵심 아이디어는 정체 구역의 경계만 처리한다는 것이다.

경계만 처리해도 내부는 방문할 수 없게 된다.

새로운 아이디어를 배워 간다.

 

E - 해시 해킹

어려운 정수론 문제처럼 보여서 넘겼다.

다시 잘 관찰하니 해시값은 항상 균등하게 분포하였다.

따라서 답은 M^(N - 1)

01:19 AC

 

G - 돈 피하지 않기 게임 (not solved)

dp로 가능해 보였는데 점화식이 상당히 복잡해져서 포기하였다.

에디토리얼에서도 구체적인 점화식은 언급하지 않길래 내 마음대로 막 짰다.

 

우선 다음과 같은 경우에는 모든 돈을 모을 수 없다.

• 동일한 높이에 3개 이상의 돈이 존재하는 경우
• 동일한 높이에 2개의 돈이 존재하는데 돈이 서로 인접하지 않는 경우
• 높이 1에 2개 이상의 돈이 존재하는 경우
• 높이 1에 돈이 존재하는데 x 좌표의 절댓값이 1보다 큰 경우

다른 경우들도 있지만 나머지는 dp 과정에서 처리할 수 있다.

 

dp 테이블은 각 높이별로 2개의 상태를 가진다.

이때 동일한 높이에 몇 개의 돈이 존재하는지에 따라 상태 정의가 달라진다.

 

동일한 높이에 1개의 돈만 존재하는 경우에는 다음과 같이 정의된다.

• dp[i][0] = i번째 높이에서 점프 없이 돈을 수집하는 경우의 최소 비용
• dp[i][1] = i번째 높이에서 점프를 하여 돈을 수집하는 경우의 최소 비용

동일한 높이에 2개의 돈이 존재하는 경우에는 다음과 같이 정의된다.

• dp[i][0] = i번째 높이에서 1번째 돈을 수집한 후 0번째 돈을 수집하는 경우의 최소 비용
• dp[i][1] = i번째 높이에서 0번째 돈을 수집한 후 1번째 돈을 수집하는 경우의 최소 비용

복잡한 상태 전이를 잘 처리해주면 된다.

대회 중에는 설마 이렇게 푸는 문제가 아니겠지 하고 코드를 전부 날렸는데 결국 이렇게 풀었다.

업솔빙 중 WA를 너무 많이 받았는데 아직 dp 실력이 많이 부족해서 그렇다.

 

끝

끝