본문 바로가기

Java9

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.
12865번 - 평범한배낭(dp) 문제:여행에 가져갈 수 있는 N개의 물건이 있다. 물건들은 각각 W의 무게와 V의 가치를 지닌다.배낭에는 최대무게 K만큼 넣을 수 있다.배낭에 넣을 수 있는 물건들의 가치의 합의 최대값을 구하여라첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000)가 주어진다. 풀이:입력으로 아래와 같이 들어왔다고 생각해보자.N=6, K=9w=6, v=13 w=4, v=8w=3, v=6w=5, v=12w=3, v=10w=3, 3=11첫 입력으로 w=6, v=13 인 짐이 들어왔고, 무게 5까지는 아무것도 담지 못한다.6 이.. 2024. 8. 15.

티스토리툴바