인프런 커뮤니티 질문&답변
작성한 질문수
4-F go 함수 안에 k가 이해가 가질 않습니다.
작성
·
378
·
수정됨
0
1062 문제에서 알파벳 26개중 k개를 가르쳤을 때, 주어진 단어를 최대로 읽을 수 를 return 하는 걸로 이해했습니다.
이중 규칙에의해 시작글자인 'anta'와 맺음 글자인 'tica'는 무조건 알아야 한다고 생각해서 'a','n','t','i','c'는 필수 배움 글자로 두고 문제를 풀었습니다.
예를 들어서 test case의 k가 6이면 위에 필수 5개를 제외하고 1개를 추가로 배울 수 있다는 걸 의미하고, 이를 바탕으로 풀었을때 test case 1은 'r'을 배우는게 2개의 단어를 읽을 수 있어 최대치 라는 결과를 얻을 수있습니다.
그런데 썜의 코드를 봤을 때, 단어를 배울때마다 k-1로 k를 1개씩 지워 k=0일 경우 단어를 비교하는 알고리즘 같은데, 필수 5개를 배우는데에 k값이 소모되지 않는 것 같아서 이해가 되질 않습니다.
제가 이해한대로 생각해보면, 쌤 코드는 필수 5개를 제외한 k개를 추가로 배울 수 있다는 논리인거같아서 제가 어디를 잘못이해하고있는지 알려주심 감사하겠씁니다...
아래는 제가 이해한대로 구현해본 코드입니다.
http://boj.kr/6327c4069bf849f3bf6ffb46ca83df39
주어진 단어집에 사용된 알파벳을 한정으로 배우는 경우의수를 계산했고, 뒤에 단어집과 비교하는 논리는 쌤과 비슷한거 같은데 시간초과가 나옵니다. 제가 시간복잡도를 잘못생각했나요?
답변 1
0
안녕하세요 ㅎㅎ
이코드를 볼까요? antatica에 해당하는 알파벳은 무조건 배워야 합니다.
그렇기 때문에 antatica에 해당하지 않은 알파벳만 "배우지 않는" 경우의 수를 고려한 것을 볼 수 있습니다.
int ret = go(index+1, k-1, mask | (1 << index));
if (index != 'a'-'a' && index != 'n'-'a' && index != 't'-'a' && index != 'i'-'a' && index != 'c'-'a') {
ret = max(ret, go(index+1, k, mask));
}수강생님의 코드를 보면 이 부분이 틀린 거 같은데요. 꼭 K개를 사용했을 때만 넣어야 할까요? K 이하라도 가능하지 않을까요?
if(cnt == k){
re.push_back(_num);
}