본문 바로가기

백준

 (227)
백준 2624 - 동전 바꿔주기 www.acmicpc.net/problem/2624 각 고유한 가치를 지닌 동전의 개수가 주어졌을 때 금액 T를 만들 수 있는지, 가능하면 경우의 수가 몇 가지가 되는지 알아내는 문제이다. 2원이 4개 있다고 할 때 다음 테이블을 고려해보자. 금액 0 1 2 3 4 5 6 7 8 경우의 수 1 0 0 0 0 0 0 0 0 초기엔 0원을 만드는 경우도 인정하여 0원을 만드는 경우의 수를 1이라고 설정해 놓는다. 여기서 2원을 하나 가지고 테이블을 채워보자. 금액 0 1 2 3 4 5 6 7 8 경우의 수 1 0 1 0 0 0 0 0 0 자명하게도 1개의 2원 동전으로는 다음과 같이 테이블을 채울 수 있을 것이다. 여기서 2원을 하나 더 추가하면 다음과 같이 된다. 금액 0 1 2 3 4 5 6 7 8 경우..
백준 3980 - 선발 명단 www.acmicpc.net/problem/3980 3980번: 선발 명단 문제 챔피언스 리그 결승전을 앞두고 있는 맨체스터 유나이티드의 명장 퍼거슨 감독은 이번 경기에 4-4-2 다이아몬드 전술을 사용하려고 한다. 오늘 결승전에 뛸 선발 선수 11명은 미리 골라두었� www.acmicpc.net 11명의 선수를 배치했을 때 최대 능력치를 구하는 문제이다. 11명을 전부 배치할 수 있는 TC만 주어지며 반드시 11명을 배치해야 한다는 점을 주의하자. 11명을 반드시 배치해야 한다는 조건에 주목하여 비트마스크 DP, 탐색 등의 방법을 통해 능력치의 최댓값을 찾도록 한다. 단, 비트마스크 DP를 이용시 다음과 같은 케이스에 유의하도록 한다. 1 10 0 0 0 0 0 0 0 0 0 0 0 10 0 0 0 0..
백준 10422 - 괄호 www.acmicpc.net/problem/10422 짝이 맞는 괄호의 개수는 카탈란 수의 잘 알려진(Well Known) 예시 중 하나이다. 카탈란 수에 대해 자세한 정보는 이 글에 있으며 $\binom{2n}{n} - \binom{2n}{n - 1} = \frac{1}{n + 1} \binom{2n}{n} = \frac{(2n)!}{(n + 1)!n!}$ 다음과 같이 3개의 식으로 사용할 수 있다. 이 문제에서는 1,000,000,007로 나눈 나머지를 구해야 하므로 페르마의 소정리를 활용하기 위해 3번째 식을 이용했다. 주의 사항은 n쌍이 아니라 n개가 입력으로 주어지므로 괄호의 개수가 홀수개일 때는 괄호 짝이 절대 만들어지지 않는다는 점과 짝수개가 주어지면 이를 괄호의 짝 개수로 치환하기 위해 2..
백준 1043 - 거짓말 www.acmicpc.net/problem/1043 1043번: 거짓말 지민이는 파티에 가서 이야기 하는 것을 좋아한다. 파티에 갈 때마다, 지민이는 지민이가 가장 좋아하는 이야기를 한다. 지민이는 그 이야기를 말할 때, 있는 그대로 진실로 말하거나 엄청나게 � www.acmicpc.net 지민이가 거짓말을 할 수 있는 파티 개수의 최댓값을 구하는 문제이다. "어떤 사람이 어떤 파티에서는 진실을 듣고, 또다른 파티에서는 과장된 이야기를 들었을 때도 지민이는 거짓말쟁이로 알려지게 된다. 지민이는 이런 일을 모두 피해야 한다." 해당 문장에 각별히 유의하여 문제에 접근해보자. 파티에서 거짓말을 할 수 있는지 알 수 있는 여부는 진실을 모르는 사람이 모든 파티에 대해 진실을 아는 사람과 만나지 않아야 함을 알..
백준 15468 - 퇴사 2 www.acmicpc.net/problem/15486 15486번: 퇴사 2 첫째 줄에 N (1 ≤ N ≤ 1,500,000)이 주어진다. 둘째 줄부터 N개의 줄에 Ti와 Pi가 공백으로 구분되어서 주어지며, 1일부터 N일까지 순서대로 주어진다. (1 ≤ Ti ≤ 50, 1 ≤ Pi ≤ 1,000) www.acmicpc.net 상담을 통해 백준이가 얻을 수 있는 최대 수익을 구해보자. N이 최대 150만으로 꽤 크므로 완전탐색은 불가능하고 동적 계획법을 통해 문제를 풀어야 한다. 다음 점화식을 세워 풀이할 수 있다. 구하려는 최대 수익 earning에 대해 earning += max(idx 일에 상담을 실시 했을 때 벌 수 있는 수익, idx 일에 상담을 하지 않을 경우 벌 수 있는 수익) 본인의 코드에..

티스토리툴바