전체 글50 [백준]RGB거리 - 복습 DP https://www.acmicpc.net/problem/1149 모든 경우의수를 계산하면 당연히 시간초과가 난다 (제한시간 0.5s) 인접한 집은 같은 색으로 칠 할 수 없다 지금 집을 Red로 칠했으면 다음 집은 Green or Blue . . . 5 4 3 2 40 + 49 26 + 60 26 + 57 1 26 40 83 R G B 이런 테이블을 기본으로 2번 집 부터 빨강을 칠한다고 생각했을때 1번집에서 가능한 G, B중 낮은값을 가져온다 이전 누적 값 중 낮은 값을 그대로 가져와도 반례는 없다. 어짜피 다음 집 색과 겹치지만 않으면 되기 때문 #include #include using namespace std; int input[1001][4]; int dp[1001][4]; int INF = .. 2021. 3. 17. [백준] 한 줄로 서기 - 복습 https://www.acmicpc.net/problem/1138 가장 큰 사람부터 맨앞에 배치하고 그 다음으로 큰 사람부터 규칙에 맞게 맨앞부터 차례대로 밀어넣는다 자기보다 작은사람이 앞에 끼어들어와도 자신보다 큰 사람의 수에는 영향을 안주기 때문 #include using namespace std; int N; void insert(int *input, int index, int value) { if (input[index] == 0) { //처음 입력되면 그냥 삽입 input[index] = value; } else {//이전에 입력된 값이 있으면 뒤에값들을 한칸씩 밀어낸다 for (int i = N-1; i > index; i--) { input[i] = input[i - 1]; } input[i.. 2021. 3. 17. [백준] 트리 - 복습 https://www.acmicpc.net/problem/1068 직관적으로 코드 구현 하였다. 실제 트리를 구성하고 제거해야 할 트리를 제거 마지막으로 BFS로 리프 노드 갯수를 센다 #include #include #include #include #define NODENUM 52 using namespace std; typedef struct _TREE_ { int val; int parent; vector child; }TREE; queue q; TREE tree[NODENUM]; int cnt; void bfs(int start) { q.push(start); while (!q.empty()) { int here = q.front(); q.pop(); // 리프 노드이면 if (tree[here].. 2021. 2. 5. [백준] 친구 - 복습(플루이드-와샬) https://www.acmicpc.net/problem/1057 플루이드-와샬 알고리즘 - 모든 정점의 최단거리를 간단하게 구할수 있다. 시간복잡도는 O(a^3) 2-친구의 수를 구한다고 했으므로 최단거리가 2이하인 값만 카운트 한다 #include using namespace std; char Graph[51][51]; int graph[51][51]; int ret[51][51]; int INF = 987654321; int main() { int N; cin >> N; for (int i = 0; i > Graph[i]; for (int i = 0; i < N; i++) for (int j = 0; j < N; j++) { if (Graph[i][j] == 'N') gr.. 2021. 2. 5. [백준] 명령 프롬프트 - 복습(c++ String) https://www.acmicpc.net/problem/1032 문제 자체는 한명령을 기준으로 잡고 나머지명령과 비교해서 마지막까지 동일한 갯수만 카운트 하였다 #include #include using namespace std; char filename[51][51]; bool check[51]; int main() { int N; cin >> N; for (int i = 0; i > filename[i]; for (int i = 0; i < 51; i++) check[i] = true; for (int i = 0; i < strlen(filename[0]); i++) { char c = filename[0][i]; int j; for (j = 1; j < N; j++) i.. 2021. 2. 4. [백준] 고층건물 - 복습(hard) https://www.acmicpc.net/problem/1027 정말로 어려웠던 문제 실제 시험을 칠때는 활용하지 못하겠지만 기하학 문제라고 분류가 되어 있으면 기하학적으로 접근하자 처음에 대수적으로 가장 높은 빌딩에서 그 다음 빌딩까지 사이의 빌딩을 카운트 하면 되겠지 하고 쉽게 생각했지만 반례도 많고 프로그래밍 하기도 까다로웠다 (인접한 빌딩이 높이가 1 차이난다면 그 다음 빌딩은?) 결국 핵심 포인트는 빌딩이 서로를 볼 수 있으려면 그 사이의 빌딩과의 기울기보다 커야 된다는 것!! #include #include int n, a[50], b[50]; int main() { scanf("%d", &n); for (int i = 0; i < n; i++){ scanf("%d", a + i); } fo.. 2021. 2. 4. 이전 1 ··· 3 4 5 6 7 8 9 다음