본문 바로가기

분류 전체보기

(297)
다리놓기 www.acmicpc.net/problem/1010 1010번: 다리 놓기 입력의 첫 줄에는 테스트 케이스의 개수 T가 주어진다. 그 다음 줄부터 각각의 테스트케이스에 대해 강의 서쪽과 동쪽에 있는 사이트의 개수 정수 N, M (0 < N ≤ M < 30)이 주어진다. www.acmicpc.net #include #include #include using namespace std; int n, m,t; long long com[30][30]; // nCr 구하기 int combi(int n, int r) { if (n == r) { return 1; } if (r == 0 || n == 0) { return 1; } if (com[n][r] != 0) { return com[n][r]; } return ..
트리의 부모찾기 www.acmicpc.net/problem/11725 11725번: 트리의 부모 찾기 루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오. www.acmicpc.net #include #include using namespace std; bool findNoMore(int num, vector&v, vector&parent) { for (int i = 0; i < v[num].size(); i++ ) { if (parent[v[num][i]] ==0) { return false; } } return true; } void dfs(vector&parent, vector&v,int num) { if (findNoMore(num,v,parent..
성냥깨비 www.acmicpc.net/problem/3687 3687번: 성냥개비 각 테스트 케이스에 대해서 입력으로 주어진 성냥개비를 모두 사용해서 만들 수 있는 가장 작은 수와 가장 큰 수를 출력한다. 두 숫자는 모두 양수이어야 하고, 숫자는 0으로 시작할 수 없다. www.acmicpc.net #include #include #include #include #include using namespace std; long long num[9] = { 0, 0, 1, 7, 4, 2, 0, 8, 10 }; int main() { int n; cin >> n; int cnt; long long mindp[101]; long long maxdp[101]; mindp[0] = 0; mindp[1] = 0; mindp[2..
퇴사 www.acmicpc.net/problem/14501 14501번: 퇴사 첫째 줄에 백준이가 얻을 수 있는 최대 이익을 출력한다. www.acmicpc.net #include #include #include #include using namespace std; int n; int dp[17]; int main() { cin >> n; memset(dp, 0, sizeof(dp)); vectort(n+2); //days vectorp(n+2); //profit for (int i = 1; i > t[i]; cin >> p[i]; } int ans = 0; for (int i = 1; i
키 순서 / 플로이드 와샬 www.acmicpc.net/problem/2458 2458번: 키 순서 1번부터 N번까지 번호가 붙여져 있는 학생들에 대하여 두 학생끼리 키를 비교한 결과의 일부가 주어져 있다. 단, N명의 학생들의 키는 모두 다르다고 가정한다. 예를 들어, 6명의 학생들에 대하여 www.acmicpc.net #include #include #include using namespace std; bool dp[501][501]; int main() { int n, m; cin >> n; cin >> m; int a, b; for (int i = 0; i > a; cin >> b; dp[a][b] = true; } int count = 0; for (int k = 1; k
우수 마을 / Tree DP www.acmicpc.net/problem/1949 1949번: 우수 마을 N개의 마을로 이루어진 나라가 있다. 편의상 마을에는 1부터 N까지 번호가 붙어 있다고 하자. 이 나라는 트리(Tree) 구조로 이루어져 있다. 즉 마을과 마을 사이를 직접 잇는 N-1개의 길이 있으며, www.acmicpc.net #include #include #include using namespace std; int n; int towns[10001]; vectorv(10001); int dp[10001][2]; bool visited[10001]; void dfs(int idx) { visited[idx] = true; dp[idx][0] = 0; dp[idx][1] = towns[idx]; for (int i = 0; ..
사회망 서비스 / Tree DP www.acmicpc.net/problem/2533 2533번: 사회망 서비스(SNS) 페이스북, 트위터, 카카오톡과 같은 사회망 서비스(SNS)가 널리 사용됨에 따라, 사회망을 통하여 사람들이 어떻게 새로운 아이디어를 받아들이게 되는가를 이해하는 문제가 중요해졌다. 사회망 www.acmicpc.net #include #include #include using namespace std; int dp[1000001][2]; bool visited[1000001]; void dfs(vector&friends, int i) { visited[i] = true; dp[i][0] = 0; dp[i][1] = 1; for (int j = 0; j < friends[i].size(); j++) { if (visite..
마법사 상어와 파이어볼 / 시뮬레이션 www.acmicpc.net/problem/20056 20056번: 마법사 상어와 파이어볼 첫째 줄에 N, M, K가 주어진다. 둘째 줄부터 M개의 줄에 파이어볼의 정보가 한 줄에 하나씩 주어진다. 파이어볼의 정보는 다섯 정수 ri, ci, mi, si, di로 이루어져 있다. 서로 다른 두 파이어볼의 위치 www.acmicpc.net #include #include #include #include #include using namespace std; int n, t, k; //0,1, int dx[] = {-1,-1,0,1,1,1,0,-1}; int dy[] = {0,1,1,1,0,-1,-1,-1}; struct info { int r; int c; int m; int d; int s; }; info ..