1. SCPC 2018 1차 예선 2 - 회문인 수의 합 더보기 풀이 처음에 알고리즘 분류를 DP로 알고 있어서 DP로 생각하다가 우주 갔다가 돌아온 문제이다. 이 문제는 브루트포스로 해결이 가능했다. 브루트포스에서 가장 중요한 점인 시간 복잡도만 체크해보자. (아이디어는 떠올리기 어렵지 않다) 먼저 n제한은 10000이고 시간 제한은 1초이다. 즉 O(n제곱)은 성립하지 않는다. 그렇다면 이곳저곳에서 컷팅을 시도해보자. 먼저 우리가 체크해야 할 것은 총 3가지 이다. 1. 자기 자신이 바로 회문인 경우 2. 2개의 회문의 합으로 이루어진 경우 3. 3개의 회문의 합으로 이루어진 경우 자기 자신이 회문인 경우는 1~10000까지 각각 체크해주면 되므로 O(1만)이다. 2번째 경우 역시 마찬가지로 1~10..
acm-icpc
1. 백준 2159번 - 케익 배달 (Gold 2 - DP) 더보기 https://www.acmicpc.net/problem/2159 2159번: 케익 배달 첫째 줄에 N이 주어지고 둘째 줄에는 선아가 일하는 레스토랑의 위치가, 셋째 줄부터는 N명의 위치가 X와 Y로 주어진다. 두 좌표 사이에는 공백이 하나 이상 있다. (1 ≤ N, X, Y ≤ 100,000) www.acmicpc.net 풀이 문제의 핵심은 크게 2가지이다. 1. 주문이 들어온 순서대로 배달되기를 원함 2. 케익을 받는 고객의 위치까지 가거나 고객의 상하좌우 인접 격자점에 가야함 1번의 조건에 따라 i번째 최단 거리는 반드시 i-1번째 최단거리의 영향을 받는다. 따라서 앞서 구했던 최단거리들을 저장해놓고 사용한다 -> Dynamic P..
1. 백준 3687번 - 성냥개비 (Gold 2 - dp, Greedy) 더보기 https://www.acmicpc.net/problem/3687 3687번: 성냥개비 각 테스트 케이스에 대해서 입력으로 주어진 성냥개비를 모두 사용해서 만들 수 있는 가장 작은 수와 가장 큰 수를 출력한다. 두 숫자는 모두 양수이어야 하고, 숫자는 0으로 시작할 수 없다. www.acmicpc.net 풀이 0~9까지의 숫자는 아래와 같은 개수의 성냥개비로 이루어진다. 0 = 6개, 1 = 2개, 2 = 5개, 3 = 5개, 4 = 4개, 5 = 5개, 6 = 6개, 7 = 3개, 8 = 7개, 9 = 6개 이 때 n개의 성냥개비로 만들 수 있는 최대의 숫자는 반드시 "1" 또는 "7"으로만 이루어진다. 왜냐하면 최대의 숫..
출처 : https://www.acmicpc.net/problem/20176 참고한 글 : https://koosaga.com/263 문제 및 풀이 3개의 선분이 위에서부터 차례대로 하나씩 있고, 각 선분 당 특정 좌표에는 구멍이 뚫려있습니다. 아래 그림은 정답이 될 수 있는 바늘이 3개의 선분을 통과한 사례입니다. 기본적으로 바늘이 3개의 선분을 지나가기 위해서는 a~b, b~c 를 지나갈 때 선분의 기울기가 같아야 하고, b의 위치가 동일해야 합니다. 즉, a+c = 2 * b 를 만족한다면 바늘은 선분을 지날 수 있습니다. (편의상, 배열 A, B, C 의 어떤 한 원소를 a, b, c 라 하겠습니다) 일반적으로 모든 a+c 를 구하기 위해선, 어쩔 수 없이 배열 A, C의 원소를 모두 순회하며 구..
1. 백준 14289번 - 본대 산책 3 (Gold 1 - 분할 정복 기법을 사용한 행렬 거듭제곱 dp 문제) 더보기 https://www.acmicpc.net/problem/14289 14289번: 본대 산책 3 가능한 경로의 수를 1,000,000,007로 나눈 나머지를 출력한다. www.acmicpc.net 풀이 결국 정보대에서 정보대까지 d번만에 가는 경우의 수를 구해야 하는 문제였다. 이를 일반화 해보면 "A 노드에서 B 노드까지 d번만에 가는 경우의 수"를 구해야 한다. 이 부분을 dp스럽게 생각해보면 "A노드에서 B와 연결된 모든 노드까지 d-1번 만에 도착하는 경우의 수들의 합"과 같다. 즉 식으로 나타내면 다음과 같다. dp[i][j][k] = i 노드에서 j 노드까지 k번 만에 도착하는..
1. 백준 1086 박성원 (Platinum V - bitmask dp 문제) 더보기 https://www.acmicpc.net/problem/1086 1086번: 박성원 첫째 줄에 정답을 기약분수 형태로 출력한다. p/q꼴로 출력하며, p는 분자, q는 분모이다. 정답이 0인 경우는 0/1로, 1인 경우는 1/1로 출력한다. www.acmicpc.net 문제 N개의 수로 이루어진 집합이 주어진다. 이 집합의 순열을 합치면 큰 정수 하나를 만들 수 있는데, 합친 수가 정수 K로 나누어 떨어지는 순열의 개수를 구하는 문제이다. * 테스트 케이스 설명 집합 {3, 2, 1} 이 주어졌는데, 이 집합으로 만들 수 있는 순열은 다음과 같이 6가지 되시겠다. {1, 2, 3}, {1, 3, 2}, {2, 1, 3..
