28354번: 링크 컷 토마토 첫째 줄에 토마토의 개수 $N$, $0$일에 연결되어 있는 토마토 쌍의 수 $M$, $0$일에 익은 토마토의 수 $K$, 연결 상태가 변하는 횟수 $Q$가 공백으로 구분되어 주어진다. $(1 \leq K \leq N \leq 200\,000;$ $0 \leq www.acmicpc.net 문제 풀이 내 첫 플래티넘 문제였다. 알고리즘은 제대로 구성해서 작성한 것 같은데, 계속 시간 초과가 나서 애먹었던 기억이 있다. 시간을 단축시키고자 BFS 방문 시 필요 없는 방문이 발생하지 않도록 조건도 체크했는데 시간 초과가 나서 며칠 동안 붙잡고 있었다. 결론적으로 탐색이 더 효율적인 자료구조로 변경하니 통과되었다. 처음엔 그래프를 ArrayList로 구현했었는데, 그래프 안에 특정 ..
16500번: 문자열 판별 첫째 줄에 길이가 100이하인 문자열 S가 주어진다. 둘째 줄에는 A에 포함된 문자열의 개수 N(1 ≤ N ≤ 100)이 주어진다. 셋째 줄부터 N개의 줄에는 A에 포함된 단어가 한 줄에 하나씩 주어진다. A에 www.acmicpc.net 문제 풀이 처음엔 단어목록(A)에 있는 단어들을 긴 단어부터 하나씩 문자열의 앞부분과 비교해서 일치하면 단어 길이만큼 삭제하고 다시 탐색하는 방식으로 접근했었는데, 단어목록에 software, soft 같이 단어 사이에 서브 스트링이 존재하는 경우 반례가 생기는 것 같다..(사실 정확한 문제점 발견 못함) 단어를 찾았다고 문자열에서 삭제한 후 다시 고려하지 않는 방식은 미처 고려하지 못하는 경우가 발생하는 것 같다. 따라서 DP 테이블을 이용..
2193번: 이친수 0과 1로만 이루어진 수를 이진수라 한다. 이러한 이진수 중 특별한 성질을 갖는 것들이 있는데, 이들을 이친수(pinary number)라 한다. 이친수는 다음의 성질을 만족한다. 이친수는 0으로 시작하지 않 www.acmicpc.net 문제 풀이 "이친수"의 조건이 되려면 아래와 같다. 1. 이진수 중에 2. 1로 시작하는 수 3. 1이 두 번 연속 있으면 안 됨 이 조건에 맞는 경우를 각 자리 별로 찾아봤을 때 일정한 규칙을 찾을 수 있었다. 이전 자리 수에서 찾은 이친수를 그대로 가져와 이용할 수 있는데, 해당 수의 끝 자리가 1로 끝나면 연속으로 1이 올 수 없으니 0만 붙일 수 있다. 반대로 0으로 끝나는 수면 0과 1을 모두 붙일 수 있다. 따라서 자릿수가 4인 이친수를 구..
📝 오늘의 일기 DP는 참 어렵다. DP는 보통 점화식을 찾아내기만 하면 코드로 옮겨 구현하는 시간은 짧은 편인데, 그 점화식을 찾아내는 방법이 연습 말고는 없는 것 같다.. 그래서 다른 알고리즘 문제풀이는 따로 포스팅을 하지 않는 편인데, DP는 잘할 때까지 포스팅하면서 정리해야 할 것 같다. 9095번: 1, 2, 3 더하기 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다. www.acmicpc.net 문제 풀이 처음엔 DP 테이블을 2차원을 구성해서, 1로만 해당 숫자를 구성하는 경우, 1과 2로 구성하는 경우, 1,2,3으로 구성하는 경우의 수를 따져 보았는데, 2차원 배열 안에선 아무리 봐도 규칙을 찾을 수 없었다. 1차원 배열로 DP 테이블을 다시 구성해서 보..
