그날그날 공부기록

시간이 없어서 후다닥 적습니다. 어떻게 풀어야할지 감이 잘 오지 않아 시간이 걸렸다. N개의 숫자가 있다고 해보자. N이 1일 경우는 1, 2, 3, 4, 5, 6, 7, 8, 9가 있다. N이 2부터 경우가 생긴다. 계단 수 = 첫 숫자 -> 다음 숫자라고 표시해보면 다음과 같다. 1? = 1 -> 0 2? = 2 -> 1 or 3 3? = 3 -> 2 or 4 ... 8? = 8 -> 7 or 9 9? = 9 -> 8 이렇게 1 ~ 8 다음에 오는 숫자는 i-1과 i+1 두 가지 경우가 올 수 있다. 9 다음에는 무조건 8이 오게된다. * 두 번째 자리부터는 0이 올 수 있지만, 앞의 수가 0이라면 다음 수는 무조건 1만 오게된다. DP[N][마지막 수]로 생각해보자. 마지막 수가 1 ~ 8일 경우 ..

9465 스티커 문제: https://www.acmicpc.net/problem/9465 문제 이해 완전탐색으로도 정답은 구할 수 있지만, n의 최댓값은 100,000이므로 시간제한에 걸리게 된다. DP로 풀기 위해 점화식을 찾아보자. 떼어낸 스티커의 상하좌우에 있는 스티커는 사용할 수 없다. 우선 간단히 생각해보면 다음 그림과 같이 대각선을 반복하는 2가지의 경우가 나온다. 이 두 가지의 경우에서 최댓값은 250이지만, 이는 전체 경우의 수에서 최댓값이 아니다. 스티커를 선택하지 않는 경우가 있기 때문이다. 다음 그림처럼 100 다음 열인 3열의 스티커를 선택하지 않는다면, 60인 스티커를 선택할 수 있어 260으로 최댓값을 구할 수 있다. 100 다음 한 열을 건너뛰고 40을 선택하는 경우는 항상 최..

문제의 예제를 필기해 보니 13164 행복유치원 문제와 유사해 보였다. 모든 센서를 수신할 수 있는, 최대 K개의 집중국들의 최소 수신 가능영역의 합을 출력하면 된다. 5 -> 센서 수 2 -> 최대 집중국 수 1 6 9 3 7 -> 센서의 좌표 좌표: 1 2 3 4 5 6 7 8 9 센서 s s s s s 각 집중국은 수신 가능 영역을 조절할 수 있기 때문에, 센서들의 길이에 딱 맞춰 설정하는 것이 최솟값일 것이다. 결국, 거리 합이 가장 적은 최대 K개의 센서 그룹을 구하고, 그 길이를 더하면 문제가 원하는 출력이 나올 것이다. 센서: 1 3 6 7 9 차이: 2 3 1 2 ===================== 센서: 1 3 /분해/ 6 7 9 차이: 2 1 2 ====================..

지난번 풀었던 문제와 동일했다. N개의 회의를 마칠 수 있는 최소 회의실의 개수를 찾아야 하는 문제이고, 우선순위 큐를 사용해서 해결했다. M개의 회의실의 타임라인이 있다고 생각해 보자. 두 가지의 경우가 나온다. 1. 회의실이 비었다면(진행 중인 회의가 끝났다면) 다음 회의를 이어서 배정. 2. 빈 회의실이 없다면, 새로운 회의실에 배정 우선순위 큐에 있는 요소들을 각 회의실의 타임라인이라고 생각하면 될 것 같다. 우선순위 큐는 회의 종료시간을 오름차순으로 설정했기 때문에, 가장 먼저 끝나는 회의가 우선적으로 출력된다. 회의실의 타임라인을 우선순위 큐라고 생각하면 다음과 같이 될 것이다. 1. 우선순위 큐의 앞에 있는 회의가 끝났다면, 제거하고 다음 회의를 큐에 추가한다. -> 같은 회의실을 이어서 사..

N명이 주어지고, K개의 그룹으로 나눈 뒤, 각 그룹의 비용 합이 최소가 되어야 한다. 저번에 풀었던 민겸 수 문제처럼 어떠한 규칙이 있을까 해서 규칙 찾는 것을 우선적으로 생각해 봤다. 1. 가장 큰 학생부터 왼쪽으로 비교하며, 비용이 커질 때 자른다. -> 결국 끝까지 탐색하지 않으면 원하는 값을 찾을 수 없다. 5 3 1 2 5 6 9 10 탐색 10 -> 9 = 비용1 10 -> 6 = 비용4 ... 2. 한 그룹에 M명에 들어가는 규칙 찾기 -> 실패 접근이 잘못된 것 같아 문제를 다시 읽고 생각을 해봤다. 1. 각 그룹의 학생들은 줄에서 인접해 있어야 한다. 따라서 인접한 학생의 연결을 끊으면 그룹이 나뉜다. i개의 연결을 끊으면 i+1개의 그룹이 나온다. 1 2 5 6 // 9 10 2. 학..