if문 처리가 굉장히 어마어마하게 귀찮았던문제 마치 ' 두 박스 ' 를 연상시킨다 좀 더 고민하면 잘 줄여낼수있을거같긴한데... https://www.acmicpc.net/problem/1744 1744번: 수 묶기 길이가 N인 수열이 주어졌을 때, 그 수열의 합을 구하려고 한다. 하지만, 그냥 그 수열의 합을 모두 더해서 구하는 것이 아니라, 수열의 두 수를 묶으려고 한다. 어떤 수를 묶으려고 할 때, 위치에 www.acmicpc.net #include #include int arr[10001] = {0}; int main(){ int n,ans=0; scanf("%d", &n); for(int i=0; i=1; i--){ if((arr[i-1]>0 && arr[i-1]!=1) || (arr[i]
2차원 DP 를 통해 풀어줄 수 있다. www.acmicpc.net/problem/4811 4811번: 알약 입력은 최대 1000개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄이며, 병에 들어있는 약의 개수 N ≤ 30 가 주어진다. 입력의 마지막 줄에는 0이 하나 주어진다. www.acmicpc.net dp[a][b]는 완벽한 상태의 알약이 a개, 반개짜리 알약이 b개일때의 문자열의 개수이다. 완벽한 알약을 하나 복용하고 반개짜리 알약으로 만들어 줄 수 있으므로, dp[a-1][b+1]의 경우가 생길 수 있고, 반개짜리 알약이 있는 경우 ( b > 0 ) 에는 반개짜리를 먹는 경우도 추가로 더해준다. 굳이 a==0 && b==0일때 탈출하지 않는 이유는 어차피 dp[a][k]에서 a가 ..
www.acmicpc.net/problem/11057 11057번: 오르막 수 오르막 수는 수의 자리가 오름차순을 이루는 수를 말한다. 이때, 인접한 수가 같아도 오름차순으로 친다. 예를 들어, 2234와 3678, 11119는 오르막 수이지만, 2232, 3676, 91111은 오르막 수가 아니다. 수 www.acmicpc.net 이 역시 2차원 디피문제이다. 무난하게 풀었다. dp[i][j]는 길이가 i인 숫자의 마지막이 j일때 만들어지는 오르막 수의 개수이다. 즉 수의 길이가 N인 오르막 수의 개수를 구하려면 dp[n][0]부터 dp[n][9]까지 더해주고 10007로 나눈 나머지를 출력해주면 깔끔하게 AC가 나오게 된다 주의할만한점으로는 계산도중에 int범위를 넘어갈거같지는 않아도 습관들이는 느낌..
3연DP. www.acmicpc.net/problem/9465 9465번: 스티커 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 n (1 ≤ n ≤ 100,000)이 주어진다. 다음 두 줄에는 n개의 정수가 주어지며, 각 정수는 그 위치에 해당하는 스티커의 www.acmicpc.net 이경우에는 1차원으로 비벼보려했는데 걍 2차원하는게 편할거같다 dp[2][123456]으로 만들어주고 dp[i][j]는 (i,j)에 있는 스티커를 땔때의 최대값이 된다. 여기서 조심해야할 점은 단순히 W나 M같은 꼴로만 탐색한다는 것이 아닌데, 이는 문제의 예시케이스에서도 볼 수 있듯이 체스의 나이트같은 위치에서도 최댓값을 가질 수 있다. 이것만 신경써주면 무난하게 AC. + 세그폴트가 안..
DP수련문제이다. www.acmicpc.net/problem/11052 11052번: 카드 구매하기 첫째 줄에 민규가 구매하려고 하는 카드의 개수 N이 주어진다. (1 ≤ N ≤ 1,000) 둘째 줄에는 Pi가 P1부터 PN까지 순서대로 주어진다. (1 ≤ Pi ≤ 10,000) www.acmicpc.net dp[i] 는 카드를 i개 구매할때의 금액의 최대값으로 설계했다. 최종답안은 당연히도 N개의 카드를 구매할때의 최대값이니 dp[n]을 출력해주면 AC. #include int max(int a, int b){ return a>b?a:b; } int dp[1234] = {0}; int input[1234] = {0}; int main(){ int n; int tmp = 0; scanf("%d", &n)..
www.acmicpc.net/problem/11724 11724번: 연결 요소의 개수 첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) 둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다. (1 ≤ u, v ≤ N, u ≠ v) 같은 간선은 한 번만 주 www.acmicpc.net 간단한 DFS 문제 무방향 그래프를 입력을 통해 만들어주고, 그 뒤에 dfs나 bfs 아무거나 하나 골라서 탐색해준다음 갯수만 세주면 된다. 나는 귀찮은관계로 클래식하게 재귀를 이용한 탐색을 사용했다. #include #include #include using namespace std; vector v[1001]; int visit[1001] = {..