Problem Solving/[C++] Boj (59) 썸네일형 리스트형 [C++] 백준 2293: 동전 1 https://www.acmicpc.net/problem/2293 조건을 보면 시간 제한과 메모리 제한이 빠듯한 문제이다.그 점을 유의하지 않으면 몇 번이나 틀릴 수 있다 ㅠㅠㅠ 문제를 보면 n가지 종류의 동전으로 가치의 합이 k가 되도록 하는 경우의 수를 구하는 문제이다. 배열의 한 축을 가치의 합으로 두면 문제가 풀릴 거 같아 그대로 진행해봤다!처음에는 동전의 종류도 배열의 한 축으로 둬서 2차원으로 생각해봤는데 풀이가 영 생각이 나지 않아서,1차원으로 바꾸어서 진행했다. 먼저 예제를 통해 시뮬레이션을 돌려보자.1원이 되는 경우: 12원이 되는 경우: 1 1 / 23원이 되는 경우: 1 1 1 / 1 24원이 되는 경우: 1 1 1 1 / 1 1 2 / 2 25원이 되는 경우: 1 1 1 1 .. [C++] 백준 9251: LCS https://www.acmicpc.net/problem/9251 모든 가능한 수열을 다 비교할경우 0.1초의 시간제한으로 인해 틀리게된다.이 문제의 경우 DP를 사용하면 편하게 풀 수 있다! 자, DP이므로 배열의 의미를 잘 지정하는 것이 중요하다. 어떤 식으로 배열을 설정하면 좋을까?이 문제는 i와 j에 각각 문자열의 문자를 대입시키고dp[i][j]의 값으로 두 문자열의 LCS를 지정하면 된다. 이 문제를 풀어보지 않았다면 i와 j에 이런 식으로 대입시키는 건 생각 못했을 거 같다. 그럼 점화식은 어떻게 구할까?dp의 경우 논리적으로 사고하기 어렵다면 시뮬레이션을 돌려보는 것이 크게 도움이 되는 경우가 많다.이 문제도 같은 경우이다. 먼저 예제의 ACAYKP를 i에, CAPCAK를 j에 대입시킨다.. [C++] 백준 12865: 평범한 배낭 https://www.acmicpc.net/problem/12865 제목을 보면 알 수 있듯이 그 유명한 배낭 문제이다. 먼저 입력을 살펴보면N: 물건의 개수 (1 ~ 100) 10^2W: 각 물건의 무게 (1 ~ 100,000) 10^5V: 각 물건의 가치 (0 ~ 1,000) 10^3K: 가방 속 최대무게 (1 ~ 100,000) 10^5 문제에서 원하는 출력은배낭에 넣을 수 있는 물건들의 가치합의 최댓값이다. 시간 제한은 2초이므로 10^8까지는 연산해도 괜찮다. DP 문제이므로 dp 배열을 만들고 각 값이 의미하는 바를 설정하는 게 중요하다.이 문제는 배낭 문제이므로 2차원 배열을 사용한다. dp[i][j]가 있을 때,i: 임의로 설정한 각 물건의 번호로 1부터 N까지 반복한다.j: 가방 속.. 이전 1 ··· 5 6 7 8 다음
