본문 바로가기

전체 글132

11058번 - dp, 규칙찾기 문제:크리보드는 kriii가 만든 신기한 키보드이다. 크리보드에는 버튼이 4개만 있으며, 하는 역할은 다음과 같다.화면에 A를 출력한다.Ctrl-A: 화면을 전체 선택한다Ctrl-C: 전체 선택한 내용을 버퍼에 복사한다Ctrl-V: 버퍼가 비어있지 않은 경우에는 화면에 출력된 문자열의 바로 뒤에 버퍼의 내용을 붙여넣는다.크리보드의 버튼을 총 N번 눌러서 화면에 출력된 A개수를 최대로하는 프로그램을 작성하시오.첫째 줄에 N(1 ≤ N ≤ 100)이 주어진다.  풀이:딱봐도 규칙을 찾아야 할듯한 문제이다.bfs나 dfs로 하기에는 경우의수가 너무나도 많아진다.A는 입력, a는 ctrl-a, c는 ctrl-c, v는 ctrl-v를 뜻한다.일단 한번 작성해보도록 하자.1A2AA3AAA4AAAA5AAAAA위와 같.. 2024. 8. 11.
1495번 - dp, Queue, TreeSet 문제:이번 공연에서는 매번 곡이 시작하기 전에 볼륨을 바꾸고 연주하려고 한다.먼저, 공연이 시작하기 전에 각각의 곡이 시작하기 전에 바꿀 수 있는 볼륨의 리스트를 만들었다. 이 리스트를 V라고 했을 때, V[i]는 i번째 곡을 연주하기 전에 바꿀 수 있는 볼륨을 의미한다. 항상 리스트에 적힌 차이로만 볼륨을 바꿀 수 있다. 즉, 현재 볼륨이 P이고 지금 i번째 곡을 연주하기 전이라면, i번 곡은 P+V[i]나 P-V[i] 로 연주해야 한다. 하지만, 0보다 작은 값으로 볼륨을 바꾸거나, M보다 큰 값으로 볼륨을 바꿀 수 없다.곡의 개수 N과 시작 볼륨 S, 그리고 M이 주어졌을 때, 마지막 곡을 연주할 수 있는 볼륨 중 최댓값을 구하는 프로그램을 작성하시오. 모든 곡은 리스트에 적힌 순서대로 연주해야 한.. 2024. 8. 11.
15989번 - dp, 규칙찾기 문제:정수 4를 1, 2, 3의 합으로 나타내는 방법은 총 4가지가 있다. 합을 나타낼 때는 수를 1개 이상 사용해야 한다. 합을 이루고 있는 수의 순서만 다른 것은 같은 것으로 친다.정수 n이 주어졌을 때, n을 1, 2, 3의 합으로 나타내는 방법의 수를 구하는 프로그램을 작성하시오.첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, 정수 n이 주어진다. n은 양수이며 10,000보다 작거나 같다. 풀이:뭔가 수학적 규칙이 있을 것 같지만, 어떤 조건이 있는지 잘 보이지 않는다.이럴때는 규칙을 찾을때 까지 써보는 것이 최고다.1234567891011121112131111211223111111211122131132111111211112211222311132133.. 2024. 8. 8.
1890번 - 점프(dp) 문제:N x N 크기의 바둑판이 있다. 각 칸에는 점프 할 수 있는 칸수가 적혀져있고, 오른쪽 또는 아래로만 이동이 가능하다.좌측상단에서 우측하단까지 이동해야한다.첫째 줄에 게임 판의 크기 N (4 ≤ N ≤ 100)이 주어진다. 그 다음 N개 줄에는 각 칸에 적혀져 있는 수가 N개씩 주어진다. 칸에 적혀있는 수는 0보다 크거나 같고, 9보다 작거나 같은 정수이며, 가장 오른쪽 아래 칸에는 항상 0이 주어진다.가장 왼쪽 위 칸에서 가장 오른쪽 아래 칸으로 문제의 규칙에 맞게 갈 수 있는 경로의 개수를 출력한다. 경로의 개수는 2^63-1보다 작거나 같다. 풀이:경로 개수는 2^63-1보다 작거나 같으므로 꽤 많은 경우의 수가 나올 수 있다.이럴때 BFS를 이용하면 메모리초과, DFS를 이용하면 시간초과가.. 2024. 8. 7.

티스토리툴바