본문 바로가기

알고리즘78

10422번- 괄호(dp, 카탈랑 수) 문제:'(' , ')'문자로만 이뤄진 문자열이 있다.길이가 L인 올바른 괄호 문자열을 구하여라.첫 번째 줄에 테스트케이스의 개수를 나타내는 T (1 ≤ T ≤ 100)가 주어진다. 두 번째 줄부터 각 테스트케이스마다 괄호 문자열의 길이를 나타내는 L이 주어진다. (1 ≤ L ≤ 5000) 각 테스트 케이스에 대해 길이가 L인 올바른 괄호 문자열의 개수를 1,000,000,007로 나눈 나머지를 출력하시오. 풀이:카탈란 수라는 개념을 코드로 작성하는 문제이다. 아래 블로그에 잘 설명이 되어있다.[알고리즘] 카탈란 수(Catalan number) (tistory.com)괄호를 직접 그리며 설명을 해보겠다.괄호의 수가능한 괄호 문자열0 2( )4( ) ( )(())6( ) ( ) ( ) (()) ( )( ) .. 2024. 8. 21.
2616번 - 소형기관차(dp) 문제: 풀이:각 소형 기관차가 끌 수 있는 객차 수를 3칸이라고 하자.객차의 수는 12개로 각 객차에 타있는 손님 수는 35, 40, 50, 10, 30, 45, 60, 20, 10, 50, 40, 70 이다.그렇다면 아래와 같은 전제를 도출할 수 있을 것이다.각 소형 기관차가 끌 수 있는 최대 인원은 연속되는 객차 3개의 인원의 합이다.고로 1~3번째 객차, 2~4번째 객차....10~12번째 객차만 고려하면 된다.두 소형 기관차가 끌 수 있는 최대 인원은 객차 6개의 인원의 합이다.고로 1~6번째 객차, 2~7번째 객차....7~12번째 객차만 고려하면 된다. 모든 소형 기관차가 끌 수 있는 최대 인원은 객차 9개의 합이다.고로 1~9번째 객차, 2~10번째 객차....4~12번째 객차만 고려하면 된.. 2024. 8. 19.
2281번 - 데스노트(dp) 문제: 풀이:'계산할 때 제일 마지막 줄은 앞으로 이름을 적을 기회가 있으므로 계산하지 않는다.' 라는 말에 유의하자.마지막까지 마지막줄은 포함해서 계산하지 않아도 된다는 말이다.즉, 판단해야할 사항은,지금 몇번째 이름을 적고있는지지금 줄에 몇개의 글자가 적어져있는지지금까지 남게 되는 칸 수의 제곱의 합이 얼마인지(마지막줄 빼고!!)나는 다음 과정과 같이 문제에 접근했다.맨 처음 이름을 기입한다.xxxxxxx             칸이 남는다면, 두번째 이름을 바로 옆에 기입한다. 아직 마지막줄이므로, 제곱의 합 0이다.xxxxxxx xxxx        또한 두번째 이름을 밑에도 기입해본다. 이때는 제곱의 합이 13 x 13일 것이다.xxxxxxx             xxxx              .. 2024. 8. 16.
5557번 - 1학년(dp) 문제: 풀이:숫자는 계산중에도 20을 넘길 수 없고 0이하로 떨어질 수도 없다.바로 코드를 작성해보자.import java.util.Scanner;public class 일학년_5557번 { static int N; static long[][] dp; public static void main(String[] args) { Scanner sc = new Scanner(System.in); N = sc.nextInt(); dp = new long[N-1][21]; int first = sc.nextInt(); dp[0][first] = 1; for (int i = 1; i 0) { .. 2024. 8. 15.

티스토리툴바