문제 파악https://www.acmicpc.net/problem/12970풀이문제가 꽤나 간단해보인다만,, 완전탐색(재귀)로 풀면 시간초과가 발생한다. O(N^2)잘 들여다보면 규칙을 찾을 수 있다.A를 기준으로 뒤에 있는 B의 개수만 신경쓰면 된다. ex) AABB = [2, 2, -, -] = 4이 규칙을 활용해 정답 문자열을 만들어 보았다.모든 자리수를 B로 채우고, 0부터 N-1 번째 자리수를 돌며 k를 업데이트하는 방향으로 구현하면 좀 더 직관적이다.좀 더 쉽게 이해하기 위해 n = 10, k = 20이라고 가정하여 아래 과정을 만족하고자 했다.i [0,n)순환 인덱스pairCounti번째 자리수가 B->A로 바뀔때 만족하는 추가 순서쌍 수k남은 순서쌍 수targetIdxaCounts[i]09..

문제 파악https://www.acmicpc.net/problem/1301풀이모든 상태를 해시맵에 담는 방법으로 풀이했더니, OOM이 발생했다 😇N의 범위 [3,5]가 상당히 한정적이므로 다차원 배열을 선언해 상태를 저장하기로 결정했다.(참고로 최대 개수인 5로 고정해 연산을 진행하였다.)또 3개가 연속하면 안 되는 제약조건 때문에 [마지막에서 두 번째 구슬 종류][마지막 구슬 종류]도 DP 배열에 반영해야 한다.그러므로 DP 배열은[1번째 구슬 개수][2..][3..][4..][5번째 구슬 개수][마지막에서 두 번째 구슬 종류][마지막 구슬 종류]로 7차원 배열을 가진다.DP 배열만 잘 선언해주면, 나머지는 풀이가 그렇게 어렵지는 않다.이미 계산한 상태(문제)의 결과를 저장해 두고, 같은 계산을 다..

문제 파악https://www.acmicpc.net/problem/1039풀이문제는 주어진 수 N의 자릿수 중 두 자리를 최대 K번까지 바꾸어가장 큰 수를 만드는 문제다.단, 교환 결과의 수가 0으로 시작하면 안 되며, 숫자 자리수가 1개인 경우 교환 자체가 불가능하다.최대 depth가 K인 트리를 탐색하는 문제라고 판단했다.BFS로 탐색하기로 결정했으며,동일한 depth(교환 횟수)의 문자열의 중복을 제거하는 것이 핵심이라고 생각했다.이 문제에서는 중복 제거를 위해 Map 자료구조를 활용했다.사용한 Map은Key : 교환 횟수 [0, K]Value : 해당 횟수에서 만들 수 있는 수들을 저장하는 집합 (Set)로 구성된다.BFS 탐색을 위해 큐를 순회하며 다음 depth에 위치를 바꾼 문자열을 삽입한다..

문제 파악https://www.acmicpc.net/problem/2132풀이트리의 지름을 활용해서 푸는 문제이다.이 문제는 가중치를 트리의 지름에 반영한다는 점이 독특하다.트리의 지름이면..? DFS를 두 번 수행해야겠다 😊임의의 정점에서 시작해 가장 많은 열매를 먹을 수 있는 경로를 찾는다.이 때, 해당 경로의 종점을 저장하자. (1번째 탐색)저장해 둔 종점에서 다시 트리 순회를 시작해 가장 많은 열매를 먹을 수 있는 경로를 찾는다. (2번째 탐색).그림으로 보면 다음과 같다. 가장 긴 경로를 찾게 되면 두번째 탐색 경로가 결국 첫 번째 경로를 포함하는 형태가 나올 것이다.그러므로 두 번째 탐색 시의 시작점, 종점 중 큰 점을 가중치와 함께 반환해 주면 정답이 나온다고 판단했다.이를 코드로 풀어 내..

문제 파악https://www.acmicpc.net/problem/1239풀이주어진 N이 [1,8]로 작은 편에 속한다.따라서 재귀로 풀이해도 문제가 없을 것으로 판단했다.핵심 구현 사항은 다음과 같다순열 배열 생성 (재귀)누적 퍼센트 저장10%, 40%, 50%의 경우, [10, 50, 100] 이 저장될 것누적 퍼센트를 순환하며 반대 방향의 누적 퍼센트가 있는지 탐색ex. 30% -> 80%가 있는지 검사 (즉 50%를 더한 값이 존재하는지 확인)참고) 퍼센트를 각도로 변환하게 될 시 소수점 문제가 있어서, 자연수인 퍼센트를 활용해야 한다 😅조금 더 코드를 보완하기 위해서는 50%를 초과하는 값들은 탐색에서 제외하는 방법을 추가할 수도 있겠다.(그 값들은 (0, 50) 구간에서 이미 판별했을 것이기..

문제 파악https://www.acmicpc.net/problem/1563풀이지각을 두 번 이상 했거나, 결석을 세 번 연속으로 하면 안 된다.다시 말하면 지각은 모든 일정에서 1번까지만 허용되고, 결석은 연속으로 2회까지만 허용되는 것이다.허용되는 출결 상태는 6개로 나눌 수 있다.지각 총 0회, 결석 누적 0회지각 총 0회, 결석 누적 1회지각 총 0회, 결석 누적 2회지각 총 1회, 결석 누적 0회지각 총 1회, 결석 누적 1회지각 총 1회, 결석 누적 2회그렇다면 이전 날의 상태에 출석 / 지각 / 결석 을 수행하면 현재 날까지의 출결 상태를 결정할 수 있겠다.지각 총 0회, 결석 누적 0회[지각 총 0회, 결석 누적 0회] (1) + 출석[지각 총 0회, 결석 누적 1회] (2) + 출석[지각 ..