4개의 댓글이 있습니다.
-
-
Taeyoon_Lee -
저도 대회가 끝난 후에는 비슷한 아이디어로 풀어보았는데, 제 컴퓨터에서는 large 데이터를 푸는데 30초 정도?는 걸렸던 것 같네요... 그리고 저는 pair로 node를 정의하는 부분을 구조체로 했는데, 의미를 명확하게 하기도 좋고, 오히려 코드도 더 짧아진 것 같습니다. .first.first 대신 .A를 쓰고 .first.second 대신 .B를 쓰니까요 ~_~
12년 전 link
-
-
정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.
hyunhwan
나름 문제가 재밌었던 대회였는데, 이야기가 없어서 먼저 이야기를 꺼내봅니다.
그 중에서 가장 재밌었던 문제는 B번 계산식 복원 문제였던것 같습니다.
제 경우에는 '사전순으로 가장 작은 수식'을 출력하는 부분을 처리하는데 많은 애를 먹었는데, 다음과 같은 아이디어와 동적계획법을 조합하여 구현을 해봤습니다.
우선 계산식을 처리하는 경우에는
일반적으로 자리올림/내림 연산의 경우가 발생하기 떄문에 낮은자리에서 높은자리 순으로 구현을 하는게 일반적인데요(보통 입력된 수식을 뒤집어서 계산하는 편이 편합니다)
서두에 언급한 조건 때문에 앞서 설명한 방법으로 구현할 경우에는, 거의 모든 경우를 헤아리게 되어 계산량을 줄이기 힘듭니다.
그래서 수식을 뒤집지 않고, 높은 자리부터 계산을 하되, 다음 자리를 계산할 때 자리 올림/내림 연산을 강제하도록 구현했습니다.
예를 들어서 설명하면 다음과 같습니다.
A, B, C, 그리고 D는 ? 가 들어가 있는 위치입니다.
높은 자리부터 계산할 경우 우선 C에 들어갈 수 있는 숫자는 1, 2가 됩니다. 따라서 1이 들어갈 경우 5+1 이 되어서 해당 자리의 값인 7을 만족하지 못합니다.
따라서 다음의 자리에서는 반드시 자리 올림 연산이 강제되야 하기 때문에 A에 들어가게 될 숫자는 6혹은 7이 됩니다. 앞의 과정과 마찬가지로 6이 될 경우 다음 자리에서는 강제적으로 자리올림 연산이 발생해야죠.
이러한 아이디어를 조합해서 상태공간을 [pos][a][b][c][carry] 로 잡아서 사전순으로 작은 수식이 올 수 있도록 구현을 하였는데, 여기서 pos는 연산하는 자리의 위치, a, b, c는 바로 앞단계에 선택된 숫자입니다.
그리고 carry는 강제적으로 자리올림을 발생해야 하는가, 아닌가를 뜻합니다.
근데 대회가 끝나고 생각해보니, c의 경우에는 a와 b 그리고 carry를 조합하면 c에 들어갈 숫자는 정해지기 때문에 굳이 c를 상태공간에 잡을 필요는 없더군요.
제가 대회 도중에 작성했던 소스코드를 첨부합니다. 다들 어떻게 짜셨는지 댓글로 달아주시면 좋을거 같습니다.
12년 전