12969번 - ABC(bfs, dp)
문제: 풀이:문자열 ABC의 유효한 쌍은 'AB', 'AC', 'BC'이다.A만 입력시에는 유효한 쌍이 없고,AB까지 입력시에는 유효한 쌍이 ABABC까지 입력시에는 유효한 쌍에 AC, BC가 추가된다.위 예시를 통해 알 수 있는 것은 아래와 같다.A 입력시 고려할 것은 없다B 입력시 앞에 있는 A의 수만 고려하면 된다.C 입력시 앞에 있는 A, B의 수를 고려해야 한다.C를 문자열의 앞 부분에 추가할 때 고려해야 할 것은 없다.즉, A의 수, B의 수, C의 수, 유효한 쌍의 수 4개를 기록해 놓으면, 다음 문자를 추가할 때 계산을 편하게 할 수 있다.계산 과정은 아래와 같다.기록한 정보를 꺼내온다.유효한 쌍의 수가 K와 같다면, "C * (N - (A + B + C의 수) ) + 만들어진 문자"를 출..
2024. 9. 13.
