kakasoo

문제 자체는 어렵지 않다, 떠올리는 발상이 좀 오래 걸릴 수 있긴 하지만, 생각을 해냈다면 그 이후는 크게 어려울 것도 없다. 나 같은 경우에는, 하나의 index를 기준으로 좌측과 우측으로 각각 내림차순으로 최장 길이 수열을 구하고, 그 둘의 합을 하나의 dp에 저장할 것이다. 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 38 39 40 41 42 43 44 45 46 47 48 49 50 #include using namespace std; int list[1000]; int dp[1000][3]; int n; int main(void) { cin >> n; for..

발상 자체가 조금 까다로운 문제이다. (그런 줄 알았는데, 내가 문제를 잘못 읽었다.) 상근이 ( 또 상근이야? )는 여러 나라를 여행할 건데, 최소한의 비행기만을 타고자 한다. A에서 B로 가는 비행기가 있다고 할 때, B에서 A로 가는 비행기는 한 종류로 취급한다. 상근이가 모든 나라로 여행을 가면서도 최소한의 비행기를 타려면 몇 번의 비행기를 타야 하는가? 여담이지만, 모든 나라를 돌면서도, 실패할 경우에 무엇을 출력하라는 말이 없는 것을 보니 test case로, 모두 성립할 수 있는 경우의 수만을 주는 것으로 보인다. 그럼 당연히 국가의 수 - 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 2..

(칸이라는 말을 들으면 유목민족이 먼저 떠오르는 건 이상한 걸까?) 가장 왼쪽 위 (0,0)이 하얀색이고, 하얀 색 위에 말이 몇 개 있는지 세라고 하니, 하얀 칸이 규칙성만 파악하면 되겠다. 가로 세로의 규칙을 파악해도 되겠지만 (가령 짝 짝 짝 짝 짝 짝- 줄이 바뀌면 홀 홀 홀 홀... 이런 식.) (0,0) 다음에 (0,2), 다음 줄에서는 (1,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 #include #include using namespace std; char map[8][8]; int ma..

바흐는 아는데 골드바흐는 처음 들었다. 그래서 알아보니까, 오일러의 친구였나보다. 골드바흐는 소수에 관한 추측들을 했는데, 이하 생략하고 그 중 하나로서 다음과 같은 추측을 해보았다. "4보다 큰 모든 짝수는 두 홀수 소수(2를 제외한 소수들)의 합으로 나타낼 수 있다." 사실 미해결된 명제이기도 하거니와, 소수를 구하는 공식도 결국 다 때려박기라 소수의 끝도 모르는데 저게 증명될 일이 있을까. 코딩러들은 이 문제를, brute force로 해봐서 모든 경우의 수가 성립함을 알 수 있을 것이다. 물론 long long int 범위 내에서... 수학은 근데 귀납을 인정 안하니 프로그래머들에겐 불가능하겠다. (빌게이츠는 세계적인 수학 난제도 증명도 했다던데?) (그 땐 빌게이츠도 프로그래머가 아니라 법대생이..

숫자가 예쁜 문제다, 14500번. 일단 문제에 대해서 간단한 해설을 쓰자면, 이건 무조건 dfs로밖에 풀 수 없는 문제다. 간단히 문제를 요약하건대, 아무 숫자가 적혀져 있는 2차원 배열이 주어질 때, 그 배열 위에 테트로미노 (이상, 위에 나와 있는 5가지 도형, 그리고 그 도형의 회전과 대칭)를 올려서 테트로미노 위에 적혀져 있는 숫자들의 합이 가장 큰 것을 구하는 문제이다. 고로 테트로미노가 4칸을 합쳐서 만든 도형이라는 특성 상, dfs든 bfs든 4칸이 되는 순간, 합을 반환하고 종료시켜야 하는데, bfs는 한 지점으로부터 상하좌우로 이동하기 때문에, 만들어진 도형이 반드시 인접할 거란 보장이 없다. 그에 반해 dfs는 한붓그리기와 같은 형태라서 안심하고 사용할 수 있다. 다만 dfs의 경우에..

질문에 있는 글인데, 너무나 잘 정리되어 있어서 가지고 왔다. (*이런 것에는 저작권이 없겠지?) 1. 가중치가 없는 최단 경로, 한 마디로 다익스트라 알고리즘을 써야 하는 게 아니면 무조건 bfs라는 것. 2. 모든 칸을 0으로 하나씩 바꿔보는 브루트 포스는, 최악의 경우 (1000 * 1000)^2의 반복이 된다. (map size = 1000 * 1000, 이고 각각의 칸이 모두 1인 경우가 있을 수 있기 때문에 1000000000000 번이다.) 3. 칸마다 방문 체크를 하는 방식으로는 풀 수 없다. 이거 참 중요한 이야기인데, 벽을 부수지 않은 세계와 벽을 부순 적 있는 세계가 있다고 가정해보자. 벽을 부수지 않은 세계를 0번 세계, 그리고 부순 세계를 1번 세계라고 할 때, 0번 세계에서 0번..

이 문제가 '브루트포스' 라는 분류를 가지고 있는 건, 내가 봤을 때 미친 짓이다. 브루트포스 방식으로도 풀 수야 있겠지만 시간초과가 미친듯이 난다. 브루트포스로, 더 이상 효율적으로 만들 수 없을 거라고 생각이 들 때까지 했는데 90%에서 시간초과였다. 그래서 다른 방식을 찾아서 했는데도 시간초과가 미친 듯이 나왔다. (그래서 데이터 구조와 STL을 적극 활용하였고, 최대공약수를 구하는 공식들도 훨씬 공부해야 했다.) 차라리 이건 '수학'만 구분으로 가지고 있는 게 낫다. 최대 값이 1000000000으로 입력될 수 있고, 같은 값이 2번 이상 입력되지 않는다고 하더라도 다른 수들과의 최대 공약수가 아무리 작아도 500000000은 나올 수 있을 텐데, 이걸 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 #include using namespace std; int memo[20] = { 1,1, }; int factorial(int num) { if (num == 0 || num == 1) return 1; if (!memo[num]) { return memo[num] = num * factorial(num - 1); } else return memo[num]; } int main(void) { int n,k; cin >> n >> k; cout

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 38 39 40 41 42 43 44 45 46 47 #include using namespace std; int n, s, sum, counted; int arr[21]; bool visited[21]; void dfs (int start) { visited[start] = true; int cur = start; sum += arr[start]; if (sum == s) { counted++; } for (int i = start + 1; i > n >> s; for (int i = 0; i > arr[i]; for (i..

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 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 #include #include using namespace std; /* push X : 정수 X를 스택에 넣는 연산이다. pop : 스택에서 가장 위에 있는 정수를 빼고, 그 수를 출력한다. 만약 스택에 들어있는 정수가 ..

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 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 #include using namespace std; int k, n; // 문제에서 요구하는 랜선의 개수를 n이라고 하고, unsigned long long int arr[10000]; // arr 배열은 처음에 주어진 초기 랜선의 길이들이다. int counted..

어려웠다. 어떻게 접근해야 할지 고민하다가 알아낸 것이, 전깃줄이 교차되는 경우의 수였다. 예제의 1부터 10까지의 전봇대를 생각해볼 때, 1부터 10까지를 배열의 index처럼 취급할 수 있을 것이다. 만약 이 index가 더 후위에 있다면, 이 인덱스에 해당하는 배열의 값도 더 후위에 있어야 한다. 즉 1이 3으로 연결되어 있다면 2부터 10까지는 적어도 4 이상과 연결되어 있어야 1과 교차하지 않는다. 그러나 문제가 생기는 것이 바로 0이었다. 만약 1이 0이라고 한다면 2 ~ 10까지는 1이상과 연결되어도 되는 것이니 아무런 문제가 없다. 그러나 만약 index 2가 0이라고 한다면, 사실 index 2는 값과 무관하게 항상 앞전과 교차할 일이 없어야 하겠지만, 컴퓨터는 이 0을 0이라는 전봇대와..