작심 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..

1039번: 교환 첫째 줄에 정수 N과 K가 주어진다. N은 1,000,000보다 작거나 같은 자연수이고, K는 10보다 작거나 같은 자연수이다. www.acmicpc.net 연산 횟수를 1씩 증가해주며 현재 횟수로 만들 수 있는 숫자들을 모두 임시 큐에 넣어주고 메인 큐가 empty할 때까지 반복한 뒤 빠져나오면 임시 큐의 값들을 전부 메인 큐에 넣어준다. 연산 횟수가 K가 되면 빠져나와 최댓값을 출력해주는데 최댓값의 default를 -1로 해주면 연산을 K번 할 수 없는 경우엔 최댓값이 변하지 않아 문제에서 바라는 대로 -1을 출력할 수 있다. ex) 숫자는 10이고 K는 1일 때 이때 주의할 점은 방문 체크하는 부분이다. 현재 메인 큐를 다 비우고 나면 다음 메인 큐에서 할 연산은 현재 메인 큐와 ..

1525번: 퍼즐 세 줄에 걸쳐서 표에 채워져 있는 아홉 개의 수가 주어진다. 한 줄에 세 개의 수가 주어지며, 빈 칸은 0으로 나타낸다. www.acmicpc.net 관리를 편하게 하기 위해 이차원 배열로 되어 있는 값들을 일차원으로 생각하면 123456780 으로 나타내는 게 목표가 된다. 빈칸의 상하좌우를 검사해주며 빈칸과 숫자를 교환하고 그 값이 목표와 일치하면 같이 저장되어 있던 횟수를 출력, 큐가 empty할 때까지도 목표를 못 만나면 -1을 출력한다. 큐에 값을 집어넣어줄 땐 빈칸과 숫자의 교환을 쉽게 하기 위해서 string 타입으로 숫자를 넣어주는데 이때 0의 위치(빈칸 위치)와 그 숫자까지 가는데 걸린 횟수도 같이 넣어준다. ex) ("360812745", 2, 이전 수의 횟수 + 1)..

9019번: DSLR 문제 네 개의 명령어 D, S, L, R 을 이용하는 간단한 계산기가 있다. 이 계산기에는 레지스터가 하나 있는데, 이 레지스터에는 0 이상 10,000 미만의 십진수를 저장할 수 있다. 각 명령어는 이 레지스� www.acmicpc.net D, S, L, R 각 경우에 맞게 값을 변형시킨 다음 그 값이 될 때까지 어떤 과정이 있었는지 배열에 저장한 뒤 그 값이 B가 되면 출력하면 된다. 여기서 주의할 점은 네 자리 레지스터라서 'L 적용 시 123이니까 231이겠지'라고 생각하면 안 된다. 123은 0123으로 취급하여 L 적용 시 1230이 된다. 처음에 잘못 생각하고 string으로 복잡하게 변형시켜주다 시간 초과 걸렸었다. 이 점만 주의해주면 굳이 string 쓸 필요 없이 ..

16397번: 탈출 첫 번째 줄에 N (0 ≤ N ≤ 99,999), T (1 ≤ T ≤ 99,999), G (0 ≤ G ≤ 99,999)가 공백 하나를 사이에 두고 주어진다. 각각 N은 LED로 표현된 수, T는 버튼을 누를 수 있는 최대 횟수, G는 탈출을 위해 똑같이 �� www.acmicpc.net 버튼 A를 누르는 경우에는 큐의 front에 +1한 값으로 비교해주고 버튼 B를 누르는 경우에는 큐의 front에 *2한 값을 조건에 맞게 변형한 뒤 비교해준다. 나는 그 조건에 맞게 변형하기 위해 이걸 string 형태로 바꾸어 0인 경우는 그냥 0으로 놔두고 나머지 경우는 맨 앞자리 수를 1 낮춰주고 stoi 함수를 이용해 int로 바꾸었다. 그렇게 하면 맨 앞자리 수가 0일 땐 생략되어 자동으로 ..