[BOJ 1316] 그룹 단어 체커
이 문제에서 말하는 그룹 단어라고 함은 다음과 같다. "ccazzzzbb는 c, a, z, b가 모두 연속해서 나타나고, kin도 k, i, n이 연속해서 나타나기 때문에 그룹 단어이지만, aabbbccb는 b가 떨어져서 나타나기 때문에 그룹 단어가 아니다." 위의 정의를 바탕으로 코드를 작성하면 된다. 만약에 문자열이 있다면, 문자열의 처음 문자부터 그룹 단어를 형성하고 있는지 확인하면 된다. 그룹 문자라면 연속적인 두 문자들이 계속 같을 것이고, 그룹 문자가 아니라면 연속적이지 않은 두 문자가 같은 문자를 가진 경우가 있을 것이다. 추가적으로, 이전의 문자를 통해서 이미 그룹 문자로 판명된 문자에 대해서는 검사할 필요가 없으므로, 별도의 bool 배열을 선언해준다. 해설코드(C++). 1 2 3 4 ..
[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..