CLOCKSYNC 문제 조언 부탁 드립니다. kwangswei 안녕하세요. 열심히 알고리즘 공부하는 직장인입니다. CLOCKSYNC 문제를 풀어보았는데, 오답이 나와서 도움을 부탁드리고자 합니다. 소스는 아래와 같습니다. 핵심 함수인 PressSwitch 에서는 순차적으로 스위치를 0번~3번 눌렀을 경우마다 다음 스위치를 재귀로 호출하였습니다. (4번 누르면 원위치로 돌아오므로..) 알고리즘에 문제는 없는지, 제가 간과한 부분은 없는지 조언 부탁 드립니다. 감사합니다~!! #include <stdio.h> #define MAX 10000000 // # 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 int switches[][16] = { {3, 3, 3, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}, {0, 0, 0, 3, 0, 0, 0, 3, 0, 3, 0, 3, 0, 0, 0, 0}, {0, 0, 0, 0, 3, 0, 0, 0, 0, 0, 3, 0, 0, 0, 3, 3}, {3, 0, 0, 0, 3, 3, 3, 3, 0, 0, 0, 0, 0, 0, 0, 0}, {0, 0, 0, 0, 0, 0, 3, 3, 3, 0, 3, 0, 3, 0, 0, 0}, {3, 0, 3, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 3, 3}, {0, 0, 0, 3, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 3, 3}, {0, 0, 0, 0, 3, 3, 0, 3, 0, 0, 0, 0, 0, 0, 3, 3}, {0, 3, 3, 3, 3, 3, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}, {0, 0, 0, 3, 3, 3, 0, 0, 0, 3, 0, 0, 0, 3, 0, 0}}; void Click( int* clocks,int num) { for ( int i = 0 ; i < 16; i++ ) { clocks[i] = clocks[i] + switches[num][i]; if ( clocks[i] == 15 ) clocks[i] = 3; } } int IsComplete(int* clocks) { for ( int i = 0; i < 16; i++ ) { if ( clocks[i] != 12 ) return 0; } return 1; } int PressSwitch( int* clocks, int num) { if ( num == 10 ) return MAX; int minCount = MAX; if ( IsComplete(clocks) ) return 0; for (int i = 0; i < 4; i++ ) { int c = PressSwitch( clocks, num + 1); if (minCount > (c+i) ) minCount = c+i; Click(clocks, num); } return minCount; } int main(void) { int T=1; // scanf("%d", &T); while ( T-- ) { // int clocks[16] = {12, 6,6,6,6,6,12,12,12,12,12,12,12,12,12,12}; int clocks[16] = {12, 9,3,12,6,6,9,3,12,9,12,9,12,12,6,6}; // for( int i = 0; i < 16; i++ ) // scanf("%d", clocks+i); int result = PressSwitch( clocks,0); if ( result == MAX ) printf("-1\n"); else printf("%d\n", result); } return 0; } 12년 전
2개의 댓글이 있습니다. kcm1700 IsComplete 체크가 num == 10보다 먼저 되어야할 것 같습니다. 12년 전 link kwangswei kcm1700 님 감사합니다. 말씀하신 대로 하니 정답 나오네요. 클릭 후에 +1 증가하여 재귀함수를 호출하니, 클릭 한 것에 대한 체크(IsComplete) 를 선행하는 것이 맞는 것 같습니다. 알고리즘을 설계하고 검증하는 단계를 좀 더 신경써야겠군요! 감사합니다~!!! 12년 전 link 정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.
kwangswei
안녕하세요. 열심히 알고리즘 공부하는 직장인입니다.
CLOCKSYNC 문제를 풀어보았는데, 오답이 나와서 도움을 부탁드리고자 합니다.
소스는 아래와 같습니다.
핵심 함수인 PressSwitch 에서는 순차적으로
스위치를 0번~3번 눌렀을 경우마다 다음 스위치를 재귀로 호출하였습니다.
(4번 누르면 원위치로 돌아오므로..)
알고리즘에 문제는 없는지, 제가 간과한 부분은 없는지 조언 부탁 드립니다.
감사합니다~!!
12년 전