본문 바로가기

백준

(148)
퇴사 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 ..
LCS www.acmicpc.net/problem/9251 9251번: LCS LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net #include #include #include #include #include using namespace std; int dp[1001][1001]; int main() { string str; string str2; cin >> str; cin >> str2; int strl = str.size(); int strl2 = str2.size(); memset(dp..
큐빙 www.acmicpc.net/problem/5373 5373번: 큐빙 각 테스트 케이스에 대해서 큐브를 모두 돌린 후의 윗 면의 색상을 출력한다. 첫 번째 줄에는 뒷 면과 접하는 칸의 색을 출력하고, 두 번째, 세 번째 줄은 순서대로 출력하면 된다. 흰색은 w, 노란 www.acmicpc.net #include #include #include #include using namespace std; enum FACE {U,D,F,B,L,R,SIZE}; // 위,아래,앞,뒤,왼,오 char arr[55]; int cube[SIZE][3][3]; char temp[3][3]; char init[7] = "wyrogb"; // 전개도 그리고 시작하기 /* U 0 1 2 3 4 5 6 7 8 L __________..
치킨 배달 www.acmicpc.net/problem/15686 15686번: 치킨 배달 크기가 N×N인 도시가 있다. 도시는 1×1크기의 칸으로 나누어져 있다. 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다. 도시의 칸은 (r, c)와 같은 형태로 나타내고, r행 c열 또는 위에서부터 r번째 칸 www.acmicpc.net #include #include #include #include #include #include using namespace std; int n, m; int arr[51][51]; vectorstore; vectorhouses; int minnum = 1e9 + 1; void checkDistance(int x, int y, vector&check) { for (auto it : hous..