-

https://programmers.co.kr/learn/courses/30/lessons/42895?language=cpp 코딩테스트 연습 - N으로 표현 | 프로그래머스 programmers.co.kr DFS 완전탐색으로 풀 수 있는 문제다. 깊이가 최대 8이므로 충분히 시간 내에 탐색할 수 있다. 특이한 점은 19행 ~ 29행으로 5, 55, 555, 5555와 같은 수를 더하거나 빼거나 곱하거나 나눌 수 있다는 것이다. 이 때 해당하는 숫자 만큼 dfs count변수에 더해줘야 한다. 어느 dfs 문제와 동일하게 백트래킹에도 신경을 잘 써줘야 한다. 기본적으로 깊이 초과시 리턴, 답을 찾을 시 리턴하는 것과 더불어 0에 곱하거나 나누는 것을 하지 않도록 25,26행에 설정해주는 것이 필요하다. D..

https://programmers.co.kr/learn/courses/30/lessons/42585 코딩테스트 연습 - 쇠막대기 | 프로그래머스 여러 개의 쇠막대기를 레이저로 절단하려고 합니다. 효율적인 작업을 위해서 쇠막대기를 아래에서 위로 겹쳐 놓고, 레이저를 위에서 수직으로 발사하여 쇠막대기들을 자릅니다. 쇠막대기와 레이저의 배치는 다음 조건을 만족합니다. - 쇠막대기는 자신보다 긴 쇠막대기 위에만 놓일 수 있습니다. - 쇠막대기를 다른 쇠막대기 위에 놓는 경우 완전히 포함되도록 놓되, 끝점은 겹치지 않도록 놓습니다. - 각 쇠막대기를 자르는 레이저는 적어도 하나 존재합니다. - 레이저는 어 programmers.co.kr 레벨 2 문제다. 왼쪽 인덱스와 카운트, 오른쪽 인덱스와 카운트를 두고 먼..

https://programmers.co.kr/learn/courses/30/lessons/62048 코딩테스트 연습 - 멀쩡한 사각형 | 프로그래머스 가로 길이가 Wcm, 세로 길이가 Hcm인 직사각형 종이가 있습니다. 종이에는 가로, 세로 방향과 평행하게 격자 형태로 선이 그어져 있으며, 모든 격자칸은 1cm x 1cm 크기입니다. 이 종이를 격자 선을 따라 1cm × 1cm의 정사각형으로 잘라 사용할 예정이었는데, 누군가가 이 종이를 대각선 꼭지점 2개를 잇는 방향으로 잘라 놓았습니다. 그러므로 현재 직사각형 종이는 크기가 같은 직각삼각형 2개로 나누어진 상태입니다. 새로운 종이를 구할 수 없는 상 programmers.co.kr 레벨 2의 문제다. 생성되는 직사각형의 개수는 gcd만큼이고, 한 직..

https://www.acmicpc.net/problem/2011 > s; dp[0] = 1; for (int i = 1; i = 1 && x

https://www.acmicpc.net/problem/11057 11057번: 오르막 수 오르막 수는 수의 자리가 오름차순을 이루는 수를 말한다. 이때, 인접한 수가 같아도 오름차순으로 친다. 예를 들어, 2234와 3678, 11119는 오르막 수이지만, 2232, 3676, 91111은 오르막 수가 아니다. 수의 길이 N이 주어졌을 때, 오르막 수의 개수를 구하는 프로그램을 작성하시오. 수는 0으로 시작할 수 있다. www.acmicpc.net DP 연습문제다. DP[자리수][끝수]라고 정했을 때 맨 윗줄 DP[1][0] ~ DP[1][9]는 모두 1로 선언해준다. 그 다음, DP[N][K] = DP[N-1][0] + DP[N-1][1] + ... + DP[N-1][K]와 같이 점화식을 구성해주면..

https://www.acmicpc.net/problem/10844 10844번: 쉬운 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 백준 DP 연습문제다. 끝 자리에 유의해서 DP[자리수][끝자리수]로 만들 수 있는 계단수를 찾으면 된다. 수가 매우 커지기 때문에 모듈러 연산을 위해 long long에 정답을 저장해야 하며, 동작과정 중 n을 만나면 계산해둔 값을 이용해 답을 출력한뒤 종료하도록 구현했다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 #include #pragma warning(..

https://www.acmicpc.net/problem/4811 4811번: 알약 문제 70세 박종수 할아버지는 매일 매일 약 반알을 먹는다. 손녀 선영이는 종수 할아버지에게 약이 N개 담긴 병을 선물로 주었다. 첫째 날에 종수는 병에서 약 하나를 꺼낸다. 그 다음, 그 약을 반으로 쪼개서 한 조각은 먹고, 다른 조각은 다시 병에 넣는다. 다음 날부터 종수는 병에서 약을 하나 꺼낸다. (약은 한 조각 전체 일 수도 있고, 쪼갠 반 조각 일 수도 있다) 반 조각이라면 그 약을 먹고, 아니라면 반을 쪼개서 한 조각을 먹고, 다른 조각은 다 www.acmicpc.net 백준 4811번 알약 문제다. DP 유형의 문제로 생각할 수 있다. DP[W][H]라고 하는 배열이 온전한 알약이 W개, 반쪽짜리 알약이 H..