본문 바로가기

코딩

 (102)
백준 2618 경찰차 boj 2618 DP[i][j] = 1번 경찰차가 i위치, 2번 경찰차가 j위치에 있을때의 최소 비용(max(i,j)의 사건까지 처리한 상황) dist(a, b)는 a번 사건 위치와 b번 사건 위치사이의 거리 (i > j 일때,)DP[i][j] = DP[i-1][j] + dist(i, i-1) (if abs(i-j) != 1) DP[k][j] = dist(k, i) (if(abs(i-j) == 1), k는 0~i-2까지 DP[i][j]는 max(i,j)번 사건까지 처리한 상황이기 때문에 DP[i][j]를 계산하기 위한 식들은 인덱스의 최대값이 max(i,j)보다 1 작아야 하므로 위의 식이 성립한다 #define _CRT_SECURE_NO_WARNINGS #include #include #include ..
백준 13325 이진 트리 BOJ 13325 일단, 노드 간의 가중치를 노드로 하는 새로운 트리를 만들고 다음과 같은 기본 아이디어를 적용한다. [어떠한 노드의 자식 노드들의 '각자의 자식 노드들의 가중치 합'은 같아야 한다] 0 3 22 3 1 3 문제의 1번예시와 비슷한 트리를 예로 들겠다. 레벨 1의 [값 3]노드가 가지고 있는 자식인 2와 3은 위의 기본 아이디어를 통해 같은 값을 가져야 한다 따라서 2는 3으로 바뀐다 또한 레벨 1의 [값 2] 노드가 가지고 있는 자식인 1과 3또한 같아야 하기 때문에 1이 3으로 바뀐다 그러면 그래프가 아래와 같이 변한다 0 3 23 3 3 3 또한 레벨 0의 노드가 가진 자식들은 가중치가 6이거나 (왼쪽), 5이다(오른쪽) 오른쪽 서브 트리가 가중치가 하나 작기 때문에 오른쪽 서브트리..
마이다스 18년 대회 5번 삼항 연산자가 얽혀있는 1 != 2 ? 3 > 4 ? 5 >= 6 ? 7 : 8 == 9 ? 10 : 11 : 12 : 13 와 같은 식의 결과값을 출력하는 문제 #define _CRT_SECURE_NO_WARNINGS #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; class Node { public : char isValue; int value = 'n'; Node* left; Node* right; Node* parent; }; pair nodes[10001]; // f, t, v int isNode[1..
마이다스 18년 대회 4번 1100 1101 이라는 숫자 (10진수로 들어옴)를 100 이라는 숫자(마찬가지로 10진수로 들어옴)를 패턴으로 때는 문제 예를들어 11001101 은 100으로 때면 1 100 1101 -> 1 1101 -> 11101 이다 이건 연속적으로 가능 해서 1101000100-> 1 10 100 0 100-> 1 10 0-> 1 100-> 1 이렇게 될 수 있다 그렇게 계산된 결과의 자리수를 구하는 문제 string으로 풀면 될까 싶었는데, 나눗셈과 쉬프트를 이용해서 풀었다. #define INT_MAX_ 2100000000; #include #include #include #include #include #include #include #include #include #include #include #i..
마이다스 18년 대회 3번 A에서 Z로 이동하는 최단거리를 찾는데 중간에 거점 last를 거쳐서 가는 최단거리를 찾는 문제 #define INT_MAX_ 2100000000; #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; int last; int N; int dist[27]; vector adj[27]; priority_queue pq; void dijkstra(int startNode) { for (int i = 1; i next.first + cost) { pq.push(make_pair(next.first + cost, next.second))..
마이다스 18년 대회 1번 ID랑 패스워드를 입력받아서 소문자/숫자로만 이루어졌는지,소문자/숫자를 하나 이상 썼는지,연속된 문자를 3개 이상 쓰지 않았는지 체크하는 문제 맞을까? 정답 체크를 할 수 없는 대회라서 잘 모르겠다 #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; string id, pw; int main() { cin >> id; cin >> pw; regex pattern("(([0-9a-z]*[0-9]+[0-9a-z]*)*)|(([0-9a-z]*[a-z]+[0-9a-z]*)*)"); if (id.lengt..
백준 2096 내려가기 메모리를 줄이는게 관건인 문제 DP를 해서 풀되, 재귀로 풀지 말고 반복문으로 푼다. DP[n][n] = number[n][n] + max(DP[n-1][n], DP[n-1][n-1], DP[n-1][n+1])여기서 최대 최소 둘다 출력해야 하니 때에 따라 max나 min을 쓰자. 여기까지는, 그리고 재귀로 짜는것까지는 매우 간단 하지만 난 왜 항상 재귀를 반복문으로 고치는게 힘들까 [현재 row에서 max나 min값을 구하기 위해선 'number의 이전 row의 값'과 'memo의 이전 row의 값' 이외엔 필요하지 않다] 를 아이디어로 반복문을 짜면 된다. 그렇게 짜고 나면 입력을 받는 number도 한 줄만 있으면 됨을 알수 있기 때문에 number에 들어가는 메모리도 절약된다. 그 후 다시 코드를..
백준 2470 두 용액 절대값 기준으로 정렬 후 이웃한 두 수 끼리만 더해서 제일 합이 작은 쌍을 출력하면 됨 절대값 기준으로 정렬하여 '이웃 끼리의 숫자만 확인하면 된다' 가 정답인 이유는 아래와 같다 만약 이웃끼리 붙은 숫자 쌍이 정답이 아닐 경우를 생각해보자 A B C D ..... 와 같은 수가 있을때 B와 D의 합이 B와 C의 합 혹은 C와 D의 합보다 절대값이 더 작다는 뜻을 의미한다. 한편 B, C, D는 아래와 같은 경우의 수가 있을 수 있다. 1. B C D 순서대로 음수, 음수, 음수 or 양수, 양수, 양수 와 같이 세 수 모두 부호가 같을 경우 2. B와 D가 다른 부호일 경우(음양양, 음음양, 양양음, 양음음) 3. B와 D가 같은 부호인데 C만 다를 경우(양음양, 음양음) 1번의 경우, B와 D의 합이..

티스토리툴바