connecting the dots

문제 www.acmicpc.net/problem/2606 2606번: 바이러스 첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수가 주어 www.acmicpc.net 풀이 DFS 가장 기본 문제. 1. 배열 만들기, 연결된 노드는 1로 2. depth 끝까지 3. 중복되지 않도록 visit 여부 확인 4. 1번 컴퓨터는 제외이므로 count-1 출력 코드 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 #include using namespace std; int n, m; int..

문제 풀이 DP사용. DFS로 푸는 사람도 많았다. 날짜를 1에서 시작하는 것보다 N에서 시작하는게 코드 구현이 더 간단하다. 경우 1. 날짜 i에 상담을 진행한 경우 -> dp[i]=dp[i+t[i]]+p[i] 2. 날짜 i에 상담을 진행하지 않은 경우 -> dp[i]=dp[i+1] 22번째 line에서 dp[i]=0; 로 작성해서 틀렸었다. 나와있는 테스트케이스는 모두 맞췄는데, 다른 부분에서 조건이 위배됐나 봄.. 코드 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 #include #include #include using namespace std; int main(){ int dp[2..

풀이 이차원배열 DP[N][K]를 기반으로 한다. DP[i][j]=DP[0][j-1]+DP[1][j-1]+ ... +DP[i][j-1] 점화식을 세웠다. for문 돌리기 전 배열 값 설정을 잘못했더니 오류 발생함. 중간에 1,000,000,000 나머지 값 저장하는 것도 잊지 않기. 코드 12345678910111213141516171819202122232425262728293031323334353637383940#include #include #include using namespace std; int main(){ int dp[201][201]={0}; int n, k; scanf("%d %d", &n, &k); for(int i=1;i

풀이 i번째 계단을 올랐을 때까지의 총 점수의 최댓값은 1. DATA[i] + DP[i-2] 2. DATA[i] + DATA[i-1] + DP[i-3] 중에서 MAX값을 구한 것이다. 예외) 마지막 계단인 n번째 계단은 꼭 올라야 하므로 n-1와 n-2 모두를 오를 수는 없다. 따라서, n-1번째 계단은 예외적으로 DP[n-1]=DATA[n-1]+DP[n-3] 이다. 코드 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 #include #include #include using namespace std; #define MAX 300 int main(){ int dp[MAX..