백준 1212번 문제가 아무리 해도 안 풀립니다.

Question

안녕하세요. 브2짜리 문제도 혼자서 못 푸는 개발자 지망생입니다.https://www.acmicpc.net/problem/1212위 문제 자체의 로직은 그다지 어렵지 않았지만 제출하는 족족 "틀렸습니다"도 아니라 "시간 초과"가 납니다.#include #include #include void print2Num(int n) { int n0 = 0, n1 = 0, n2 = 0; if (n >= 4) { n0 = 1; n -= 4; } if (n >= 2) { n1 = 1; n -= 2; } if (n == 1) n2 = 1; printf("%d%d%d", n0, n1, n2); } int main() { char* input = (char*)calloc(333335, sizeof(char)); scanf("%s", input); if ((input[0] - '0') >= 4) { for (int i = 0; i < strlen(input); i++) { print2Num(input[i] - '0'); } } else { if ((input[0]) == '3') printf("11"); else if ((input[0]) == '2') printf("10"); else printf("1"); for (int i = 1; i < strlen(input); i++) { print2Num(input[i] - '0'); } } free(input); return 0; }C로 작성한 코드이고 제가 보기에는 O(n)으로 동작하는 것 같습니다. 그리고 군더더기도 안 보이는 것 같고 나름 깔끔하게 잘 작성했다고 생각합니다.하지만 이걸 제출하자마자 시간초과가 나네요. 입력으로 주어지는 수의 길이가 333,334 라는 극악의 입력이 주어지기는 하지만 코드만 잘 짜면 될 거라 생각해서 했는데 시간초과가 납니다.하다하다 안 돼서 양심에 찔리지만 결국 다른 사람의 풀이를 보고 배껴서도 해봤지만#include #include #include int main() { char* input = (char*)calloc(333335, sizeof(char)); scanf("%s", input); char** SulMa = (char**)calloc(8, sizeof(char*)); for (int i = 0; i < 8; i++) SulMa[i] = (char*)calloc(4, sizeof(char)); strcpy(SulMa[0], "000"); strcpy(SulMa[1], "001"); strcpy(SulMa[2], "010"); strcpy(SulMa[3], "011"); strcpy(SulMa[4], "100"); strcpy(SulMa[5], "101"); strcpy(SulMa[6], "110"); strcpy(SulMa[7], "111"); if ((input[0] - '0') >= 4) { for (int i = 0; i < strlen(input); i++) { printf("%s", SulMa[input[i] - '0']); } } else { if ((input[0]) == '3') printf("11"); else if ((input[0]) == '2') printf("10"); else printf("1"); for (int i = 1; i < strlen(input); i++) { printf("%s", SulMa[input[i] - '0']); } } return 0; }이렇게 배열로 했는데도 바로 시간초과가 나니까 정말 어떻게 해야할지 모르겠습니다. 차라리 자바같은 언어라면 위처럼 하자마자 출력을 하면 자바는 출력이 느리니까 버퍼에 담았다가 출력하는 방식으로 하면 될 거 같은데 C는 입출력도 빠르다보니 개선할 여지가 전혀 안 보이네요.이게 제가 뭔가 실수를 했을 거 같긴 한데 아무리 해봐도 잘 모르겠네요 도와주셨으면 합니다.감사합니다.

스토리 · Accepted Answer

조건을 검사할 때 마다 strlen(input)이 호출 됩니다.strlen(input)은 O(N) 입니다.

백준 1212번 문제가 아무리 해도 안 풀립니다.

1개의 답변

기술 목록