작심 24/7

11057번: 오르막 수 오르막 수는 수의 자리가 오름차순을 이루는 수를 말한다. 이때, 인접한 수가 같아도 오름차순으로 친다. 예를 들어, 2234와 3678, 11119는 오르막 수이지만, 2232, 3676, 91111은 오르막 수가 아니다. 수� www.acmicpc.net 수의 길이가 증가할 때마다 고정되어 있는 것은 수의 맨 뒷자리이므로 맨 뒷자리를 기준으로 표를 그려보면 한 자릿수일 때 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 두 자릿수일 때 0 1 2 3 4 5 6 7 8 9 00 01 02 03 04 05 06 07 08 09 11 12 13 14 15 16 17 18 19 22 23 24 25 26 27 28 29 33 34 35 36 37 38 39 44..

1699번: 제곱수의 합 어떤 자연수 N은 그보다 작거나 같은 제곱수들의 합으로 나타낼 수 있다. 예를 들어 11=32+12+12(3개 항)이다. 이런 표현방법은 여러 가지가 될 수 있는데, 11의 경우 11=22+22+12+12+12(5개 항)도 가능하다 www.acmicpc.net 동전 2 문제와 같은 방식으로 점화식 DP[n]=최솟값(DP[n], DP[n-현재 제곱수] + 1) 으로 풀면 되는 문제이다. 제곱수들을 동전으로 생각하고 자연수 N을 목표하는 가치 K로 생각하면 된다. N이 13이라면 제곱수들은 1, 4, 9로 이루어져 있어야 하고 N이 50이라면 제곱수들은 1, 4, 9, 16, 25, 36, 49로 이루어져 있어야 한다. 이 제곱수들을 조합하여 1~N까지의 수를 만들어 나가며 필요한 ..

2294번: 동전 2 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. 가치가 같은 동전이 여러 번 주�� www.acmicpc.net 1~K원을 만들 수 있는 동전의 개수의 최솟값을 배열에 갱신시키며 답을 구해야 하는 DP문제이다. 동전의 가치를 오름차순으로 정렬시킨 후 작은 동전부터 표를 채워나간다. 먼저 1~K원을 만드는데 필요한 1원짜리 동전의 개수를 배열에 넣는다. DP 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 1 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 5 12 그 다음 1~K원을 만드는데 필요한 ..

9465번: 스티커 문제 상근이의 여동생 상냥이는 문방구에서 스티커 2n개를 구매했다. 스티커는 그림 (a)와 같이 2행 n열로 배치되어 있다. 상냥이는 스티커를 이용해 책상을 꾸미려고 한다. 상냥이가 구매한 스티 www.acmicpc.net 문제에 나와있는 예제로 스티커가 2행 1열까지라고 생각할 때 두 가지 경우로 나눌 수 있다. 1. [0][0]을 선택하는 경우 [0][0]=50 Sticker [0] [0] 50 [1] 30 2. [1][0]을 선택하는 경우 [1][0]=30 Sticker [0] [0] 50 [1] 30 여기서 1은 [0][0]에 저장하고 2는 [1][0]에 저장한다. 스티커가 2행 2열이라고 생각할 때도 이렇게 두 가지 경우가 나온다. 1. [0][1]을 선택하는 경우 [1][0..

2178번: 미로 탐색 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. www.acmicpc.net 각 위치까지 가는데 얼마나 걸리는지 저장하다가 그 위치가 N-1, M-1일 때 출력시키면 된다. 0,0부터 시작하기 때문에 i,j에 0,0부터 넣어주고 상하좌우를 검사하며 maze의 값이 1이고 방문하지 않은 곳인 x, y을 찾은 뒤 i, j의 값+1을 넣고 방문에 체크해주고 x, y를 큐에 넣어준다. 이 과정이 끝나면 큐를 pop시켜주고 front에 있는 값을 i, j로 만든 다음 반복한다. #include #include #include #include using namespace std;..

9029번: 정육면체 입력은 표준입력(standard input)을 통해 받아들인다. 입력의 첫 줄에는 테스트 케이스의 개수 T (1 ≤ T ≤ 20) 가 주어진다. 각 테스트 케이스에 대해 원목의 크기를 나타내는 W,L,H (1 ≤ W, L, H ≤ 200) �� www.acmicpc.net 규칙을 찾으면서 너무 어렵게 생각하려고 하면 풀기 힘든 문제이다. DP로 W, L, H가 1, 1, 1일 때부터 200, 200, 200일 때까지 값을 모두 구해놓고 풀어야 한다. 설명하자면, 이렇게 그림에 나와있는 것처럼 직육면체를 두 조각으로 자르는 것에 주목해보자 H를 1 기준으로 자른 조각들은 W, L, 1와 W, L, H-1가 되고 W, L, 1에서 얻을 수 있는 정육면체의 최소 개수와 W, L, H-1에..

1912번: 연속합 첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다. www.acmicpc.net 수열의 i번째의 위치에 있을 때 num[i]에 max(i번째의 값, i-1번째까지의 최댓값 + i번째의 값) 을 넣어주면 i번째까지의 최댓값이 저장된다. 여기서 i번째까지의 최댓값이 무조건 답이 아니기 때문에 Max를 만들어 계속 최댓값을 비교하여 찾아주고 출력하면 된다. #include #include using namespace std; int main() { int N, num[100001] = { 0 }, Max; cin >> N >> num[0]; Max = nu..

2156번: 포도주 시식 효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 같은 두 가지 규 www.acmicpc.net 백준 계단 오르기 문제와 비슷하길래 비슷하게 풀려고 했다가 망해서 다른 풀이들 참고해서 풀었다. 시작 위치와 끝 위치는 어디든 상관이 없는 대신 3연속 마시기는 불가능하다. 현재 와인이 i번째에 있다고 할 때 그 위치가 세가지 경우로 나누어진다. 0번 연속인 경우 -> 0번이니까 현재 와인을 마시지 않는 것이므로 res[i-1] 1번 연속인 경우 -> 현재 와인을 마시고 그 전 와인은 마시지 않은 상태이다. 그리고 그 전 전 와인은 마시든 말든 상관이 없으므로 w..