C++[백준] 1316번 그룹 단어 체커
https://www.acmicpc.net/problem/1316 1316번: 그룹 단어 체커 그룹 단어란 단어에 존재하는 모든 문자에 대해서, 각 문자가 연속해서 나타나는 경우만을 말한다. 예를 들면, ccazzzzbb는 c, a, z, b가 모두 연속해서 나타나고, kin도 k, i, n이 연속해서 나타나기 때 www.acmicpc.net 솔루션 문자열을 입력을 받고, 해당 알파벳들을 방문처리를 한다. 만약 특정 지점에서 이미 방문 된 알파벳이 나왔는데, 그 알파벳이 이전 알파벳과는 다르다면 그룹 단어의 갯수를 줄인다. 각 테스트 케이스에서 그룹단어가 아닌 개수를 빼고 난 나머지를 출력한다. 코드 #include using namespace std; int main() { ios_base::sync_..
C++[백준]1989번 부분배열 고르기 2
https://www.acmicpc.net/problem/1989 1989번: 부분배열 고르기 2 크기가 N(1 ≤ N ≤ 100,000)인 1차원 배열 A[1], …, A[N]이 있다. 어떤 i, j(1 ≤ i ≤ j ≤ N)에 대한 점수는, (A[i] + … + A[j]) × min{A[i], …, A[j]}가 된다. 즉, i부터 j까지의 합에 i부터 j까지의 최솟값을 곱 www.acmicpc.net 솔루션 일전에 https://www.acmicpc.net/problem/2104 "부분배열 고르기" 문제를 푼 기억이 있어서 이를 참고해 풀었다. 이 문제를 스택을 이용해서 푼다면 (히스토그램) 더 빠르겠지만, 나는 조금 더 이해가 쉬웠던 분할 정복으로 해결했다. 먼저 시작점, 끝점을 받아서 중간 값을 ..