connecting the dots

문제 www.acmicpc.net/problem/2667 2667번: 단지번호붙이기 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여 www.acmicpc.net 풀이 1. 완전탐색을 통해 arr[i][j]=1인 가구를 찾는다. 2. 방문한 가구의 값은 key 값으로 바꾸고, 단지 내 다른 가구들을 찾는다.(dfs) 3. for문을 통해 같은 key값을 갖는 가구들 수를 세어 배열에 넣는다.(arrSize 배열) * - isInside 함수를 사용해 boundary를 벗어나지 않는지를 체크한다. - 처음 단지 별 key값을 1,2,3으로 하려고 했으나, key를 1로..

문제 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[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..