13560번: 축구게임 - 탐욕법 하나의 팀은 다른 모든 팀과 정확히 한 번씩만 경기를 하고 무승부는 없을 때의 팀별 승수가 주어졌을 때유효한 조합인 지 파악하는 문제이다. O(N)에 푸는 방법은 아래와 같다. Fulkerson Chen Anstee theorem: i는 1부터 N까지 일 때, ΣA[i] ≤ i*(i-1)/2 이며, ΣA[i] = N*(N-1)/2 이여야한다. 위를 만족할 경우 1, 아닐 경우 -1을 출력해주면 되는 문제이다. 또한 탐욕법으로 O(N^2)에 풀 수도 있는데매 단계마다 승수가 가장 높은 팀은 승수가 낮은 팀에 대해 이긴다라는 방법을 선택하여모든 팀에 대하여 진행해주면 풀 수 있는 문제이다.
1222번: 홍준 프로그래밍 대회 - 수학 N개의 수가 주어질 때 이들 중 X로 나누어 떨어지는 수의 개수 * X의 값의 최대값을 출력하는 문제이다.N은 최대 200,000이며 수의 최대값은 2,000,000으로 N^2으로 보는 방법은 당연히 시간 초과이다.풀이는 이러하다. 2,000,000여개를 담을 수 있는 배열 A을 만든 뒤 이 배열에는 수들의 개수를 담는다.그 다음 1 ~ 2,000,000를 보며 지금 보는 수를 X라 할 때 A[X], A[2*X], A[3*X] ... 의 값을 더한다면X로 나누어 떨어지는 수의 개수가 된다.이들 중 2이상인 수에 대해 X와 곱한 값이 가장 큰 값을 출력하면 풀 수 있는 문제이다. 이 때의 시간복잡도를 계산해보면 2,000,000개의 모든 수를 X가 1일 때는 2,..
3051번: 군사 기지 - 계산 기하 N개의 선분이 주어질 때, 세 명의 사람이 한 선분 위에 있지 않으나세 명의 사람이 이어져 있을 수 있는 방법의 가지 수를 묻는 문제이다. 즉 쉽게 얘기하면 N개의 선분을 그렸을 때 그 위에서 찾을 수 있는 삼각형의 개수이다.처음에는 N개의 선분에서 3개를 골라 이들이 삼각형을 이루는 지 확인하였다.선택한 세 선분 a, b, c로 삼각형을 만들 수 있는 지 확인하는 방법은 다음과 같이 진행하였다. 1. a와 b, b와 c, c와 a는 교점을 가진다.2. a와 b의 교점이 c 위에 있어서는 안된다. 이렇게 문제에 접근 할 경우 문제가 되는 경우는 평행한 두 선분이 합쳐질 수 있을 때이다.즉, a = (0, 2), b = (0, 4), c = (0, 3), d = (0,..
3044번: 자전거 경주 준비하기 - 위상정렬 N개의 마을이 M개의 일방통행 도로로 연결되어 있을 때1번 마을에서 시작하여 2번 마을로 끝나는 경로의 수를 구하는 문제이다. 접근 방법은 다음과 같다.1번 마을에서 X번 마을까지의 경로의 수는 X번 마을이 도착점으로 연결되어 있는 마을의 경로의 수의 합과 같다.즉 X번 마을이 도착점으로 연결되어 있는 마을의 경로의 수를 모두 구한다면 이들을 합하여 구할 수 있을 것이다.이는 그래프를 위상정렬한 순서대로 경로의 수를 구해주면 된다는 것을 알 수 있다. 먼저 1번 마을부터 2번 마을로 갈 수 있는 간선들만 모은 그래프를 다시 재생성 하여야 한다.이유는 위상정렬은 사이클이 없는 방향 그래프(DAG)에서만 할 수 있는데사이클이 있으면 무조건 inf를 출력해줘야한다..
2014번: 소수의 곱 - 우선순위 큐 K개의 소수들을 중복을 허용하여 곱했을 때의 값들을 오름차순으로 나열했을 때,N번째 오는 수를 출력하는 문제이다. 가장 먼저 생각나는 방법은 수들을 정렬한 뒤 가장 작은 수를 제거하고,그 수를 이용하여 만들 수 있는 수들을 추가하여 정렬해주면 될 것이다.예제와 같이 수 2, 3, 5, 7을 이용하여 수를 만든다면처음에는 2를 제거하고 2*2, 2*3, 2*5, 2*7값인 4, 6, 10, 14을 추가해주며 정렬한다.그러면 3, 4, 5, 6, 7, 10, 14가 될 것이며 또 3을 제거한 뒤3*2, 3*3, 3*5, 3*7값인 6, 9, 15, 21을 추가하여 정렬해주면 될 것이다.원소를 추가/제거를 하면서 반복적으로 정렬을 해야하기에 우선순위 큐를 사용하면 효율적..
1351번: 무한 수열 - DP N, P, Q가 주어질 때,A[0] = 1A[i] = A[i/P] + A[i/Q]인 점화식을 만족하는 A[N]을 구하는 문제이다. 이와 같이 간단한 점화식은 중복되는 부분문제를 저장하는 DP기법을 사용하려고 접근하지만N이 최대 10^12이기에 부분문제를 저장하는 배열을 선언할 수 없다.그러나 점화식을 자세히 보면 i가 계속 P, Q로 나누어지는데P와 Q가 최소값인 2일 때에도 2^40 >= 10^12이기에 각각 40보다 많은 항을 보지 않는 것을 알 수 있다.이에 부분문제를 담는 배열을 지수에 대한 값을 인자로 두어dp[41][41]와 같이 표현한 뒤 점화식을 세워 문제를 풀 수 있다. 또다른 방법으로는 적은 값만 참조하기에 map을 이용하여value값이 0이라면 값을 업..
3955번: 캔디분배 - 선형 다오판토스 방정식, 확장 유클리드 알고리즘 구매하고 싶은 캔디는 K*X+1개이며 사탕 한 봉지에 사탕이 C개 들어있을 때 몇 봉지를 사야할 지 묻는 문제이다. 이 때 이를 수식으로 적어보면 K*X+1 = C*N가 되며 이 수식을 만족하는 10^9이 넘지 않는 N을 구해주면 된다.K*X+1 = C*N는 C*N - K*X = 1로 변환 될 수 있다. 이 형태는 일차부정방정식의 형태로,먼저 선형 다오판토스 방정식에 의하여 일차부정방정식 ax + by = c이고 d = gcd(a, b)라 할 때d | c 즉 c를 d로 나누었을 때 나누어떨어지지 않는다면 해가 존재하지 않으며,그렇지 않다면 해가 무수히 존재하며 이 수식을 만족하는 하나의 특수 해를 구한다면 일반 해를 구해낼 수 있다..
1837번: 암호제작 - 문자열의 나머지 구하기 P와 K를 입력받아 P라는 숫자가 소수 p,q의 곱으로 나타내질 때,p와 q 중 하나라도 K보다 작은 p, q가 있을 경우 BAD와 두 소수 중 작은 소수를 출력하고없을 경우 GOOD을 출력하면 되는 문제이다. 간단하게 생각해보면 K범위가 10^6까지 이므로 10^6까지의 모든 소수를 에라토스테네스 체를 이용하여 구한 뒤P라는 수에 그 소수들을 하나하나 나누어 본 뒤 하나라도 나누어진다면 BAD,안나누어진다면 GOOD을 출력하면 되는 간단한 문제이다. 이 때 문제가 되는 부분은 P의 범위가 10^100으로 int, long long 자료형으로는 받을 수 없기에이를 문자열을 사용해서 받아야한다. 이 때 문자열을 정수로 나눈 나머지를 나머지 연산을 이용하여re..