'📒 코테연습장/📝 DP' 카테고리의 글 목록

[Baekjoon] 백준 16500_문자열 판별 (Java)

2023.07.15

16500번: 문자열 판별 첫째 줄에 길이가 100이하인 문자열 S가 주어진다. 둘째 줄에는 A에 포함된 문자열의 개수 N(1 ≤ N ≤ 100)이 주어진다. 셋째 줄부터 N개의 줄에는 A에 포함된 단어가 한 줄에 하나씩 주어진다. A에 www.acmicpc.net 문제 풀이 처음엔 단어목록(A)에 있는 단어들을 긴 단어부터 하나씩 문자열의 앞부분과 비교해서 일치하면 단어 길이만큼 삭제하고 다시 탐색하는 방식으로 접근했었는데, 단어목록에 software, soft 같이 단어 사이에 서브 스트링이 존재하는 경우 반례가 생기는 것 같다..(사실 정확한 문제점 발견 못함) 단어를 찾았다고 문자열에서 삭제한 후 다시 고려하지 않는 방식은 미처 고려하지 못하는 경우가 발생하는 것 같다. 따라서 DP 테이블을 이용..

📒 코테연습장/📝 DP

[Baekjoon] 백준 2193_이친수 (Java)

2023.07.09

2193번: 이친수 0과 1로만 이루어진 수를 이진수라 한다. 이러한 이진수 중 특별한 성질을 갖는 것들이 있는데, 이들을 이친수(pinary number)라 한다. 이친수는 다음의 성질을 만족한다. 이친수는 0으로 시작하지 않 www.acmicpc.net 문제 풀이 "이친수"의 조건이 되려면 아래와 같다. 1. 이진수 중에 2. 1로 시작하는 수 3. 1이 두 번 연속 있으면 안 됨 이 조건에 맞는 경우를 각 자리 별로 찾아봤을 때 일정한 규칙을 찾을 수 있었다. 이전 자리 수에서 찾은 이친수를 그대로 가져와 이용할 수 있는데, 해당 수의 끝 자리가 1로 끝나면 연속으로 1이 올 수 없으니 0만 붙일 수 있다. 반대로 0으로 끝나는 수면 0과 1을 모두 붙일 수 있다. 따라서 자릿수가 4인 이친수를 구..

📒 코테연습장/📝 DP

[Baekjoon] 백준 9095_1,2,3 더하기 (Java)

2023.07.08

📝 오늘의 일기 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 테이블을 다시 구성해서 보..

[Baekjoon] 백준 16500_문자열 판별 (Java)

[Baekjoon] 백준 2193_이친수 (Java)

[Baekjoon] 백준 9095_1,2,3 더하기 (Java)

티스토리툴바