[BOJ 1062] 가르침(시간초과, C++, 40% 틀린이유)
이 문제는 브루트포스 탐색을 통해서 문제를 해결하면 된다. 처음에, 문제를 풀었을 때는 시간초과가 발생했다. 문제의 조건을 살펴보면, "남극언어의 모든 단어는 "anta"로 시작되고, "tica"로 끝난다." 라는 표현이 있다. 이 말의 뜻은, a, n, t, i, c은 무조건 가르쳐야 한다는 것을 의미한다. 만약에, a, n, t, i, c의 문자를 브루트포스 탐색에서 선택 및 제외(조합)할 수 있도록 한다면 시간초과가 발생한다. 이제는 40%대의 실패에 대해서 말씀드리려고 한다. 개인적으로 처음에 문제를 좀 더 효율적으로 풀기 위해서, anta[*]tica, [*]에 해당하는 문자열들의 알파벳들을 모두 확인해서, 이 알파벳들을 배워야하는 문자들이라고 정의하자. 배워야하는 문자들 > K인 조건을 만족하..
[BOJ 1541] 잃어버린 괄호
여기서 주목해야 할 점은, 두 연산자가 반복해서 나오지 않는다는 것이다. 즉, 교대로 연산자가 나타나게 된다. 만약에 처음 연산자가 + 라면, a + b - c + d - e + f, 여기서 최소의 값을 얻으려면, a + b - (c + d) - (e + f) 형태로 괄호를 치면되고, 즉 b말고 c, d, e, f는 모두 빼주면 된다는 것이다. 나머지 경우인 처음 연산자가 - 라면, a - b + c - d + e - f a - (b + c) - (d + e) - f a를 제외하고 나머지 b, c, d, e, f에 대해서 모두 빼주면 된다. 이 문제가 그리디인 이유는, 모든 경우를 보지 않고 +를 먼저 계산하게끔 괄호를 치면 정답을 구할 수 있기 때문이다. 해설코드(C++). 1 2 3 4 5 6 7 8..
[BOJ 2533] 사회망 서비스(SNS)
이 문제는 풀지 못해서, 구글링을 통해서 문제를 해결했다. 문제에 명시적으로 나타나지 않은 부분이 있다면, Root는 항상 1번으로 표현된다는 것이다. 위의 그림을 통해서, Root Node가 1번이라는 것을 표현해주고 싶었다고 생각하면 그럴듯하다... 무튼, Root가 1번이므로, 주어진 관계를 이용해서, 트리구조로 변형해야 한다. 어떤 노드들을 선택해야 최소의 얼리어답터를 구할지 모르기 때문에, 전체탐색이 필요하다. 전체 탐색을 할 때, 메모이제이션을 통해서 DP를 사용할 것이다. DP[i][j] = i번째 Node, 얼리어답터의 유무(j)에 대한 최소 선택 얼리어답터 수 을 식으로 사용할 것이다. 현재 노드가 얼리어답터인지 아닌지에 따라서, 호출되어야 할 함수가 다르다. 추가적으로 참고해야 할 사항..
