나의 공부장

문제 링크: https://www.acmicpc.net/problem/2798 2798번: 블랙잭 문제 카지노에서 제일 인기 있는 게임 블랙잭의 규칙은 상당히 쉽다. 카드의 합이 21을 넘지 않는 한도 내에서, 카드의 합을 최대한 크게 만드는 게임이다. 블랙잭은 카지노마다 다양한 규정이 있다. 한국 최고의 블랙잭 고수 김정인은 새로운 블랙잭 규칙을 만들어 상근, 창영이와 게임하려고 한다. 김정인 버전의 블랙잭에서 각 카드에는 양의 정수가 쓰여 있다. 그 다음, 딜러는 N장의 카드를 모두 숫자가 보이도록 바닥에 놓는다. 그런 후에 딜러는 숫자 M을 크게 www.acmicpc.net 문제 풀이 카드의 합이 M을 넘지 않는 한도 내에서, 카드의 합을 최대한 크게 만들면 됩니다. 카드가 1 ~ N장이 있을 때,..

문제 링크: https://www.acmicpc.net/problem/14499 14499번: 주사위 굴리기 첫째 줄에 지도의 세로 크기 N, 가로 크기 M (1 ≤ N, M ≤ 20), 주사위를 놓은 곳의 좌표 x y(0 ≤ x ≤ N-1, 0 ≤ y ≤ M-1), 그리고 명령의 개수 K (1 ≤ K ≤ 1,000)가 주어진다. 둘째 줄부터 N개의 줄에 지도에 쓰여 있는 수가 북쪽부터 남쪽으로, 각 줄은 서쪽부터 동쪽 순서대로 주어진다. 주사위를 놓은 칸에 쓰여 있는 수는 항상 0이다. 지도의 각 칸에 쓰여 있는 수는 10을 넘지 않는 자연수 또는 0이다. 마 www.acmicpc.net 문제 풀이 주사위를 표현할 수 있는 2차원 배열 dice를 만들어서 문제를 해결했습니다. dice[4][3]이라고 ..

문제 링크: https://www.acmicpc.net/problem/1182 1182번: 부분수열의 합 첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 20, |S| ≤ 1,000,000) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는 정수의 절댓값은 100,000을 넘지 않는다. www.acmicpc.net 문제 풀이 예를 들어 {1, 2}의 부분 수열은 다음과 같다. 공집합, {1} , {2} , {1, 2} = 4개(2^2) 이러한 부분 수열들을 다 만들려면, 해당 숫자를 포함을 시킬지 안 할지를 결정해서 더 해주면 된다. 주의할 점이, 공집합은 0이랑 결과값이 같기 때문에 만약에 s가 0이라면 -1을 해줘야 한다. 이는 모든 수열에서 해당 숫자를 ..

문제 링크: https://www.acmicpc.net/problem/1018 1018번: 체스판 다시 칠하기 첫째 줄에 N과 M이 주어진다. N과 M은 8보다 크거나 같고, 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 보드의 각 행의 상태가 주어진다. B는 검은색이며, W는 흰색이다. www.acmicpc.net 문제 풀이 N X M 판에서, 8 X 8 판을 떼어내서 체스판이 되게 다시 칠해주는 작업을 할 때 그 횟수가 최소가 되는 부분을 찾아내는 문제입니다. 문제를 잘게 쪼개서 보면 다음과 같이 정리할 수 있습니다. 1. N X M을 8 X 8의 크기로 잘라낸다. (수많은 체스판들이 나옵니다.) 2. 잘라난 체스판을 가장 왼쪽 위가 흰색인 부분과, 가장 왼쪽 위가 검정색인 부분을 나눈..

문제 링크: https://www.acmicpc.net/problem/2309 2309번: 일곱 난쟁이 아홉 개의 줄에 걸쳐 난쟁이들의 키가 주어진다. 주어지는 키는 100을 넘지 않는 자연수이며, 아홉 난쟁이의 키는 모두 다르며, 가능한 정답이 여러 가지인 경우에는 아무거나 출력한다. www.acmicpc.net 문제 풀이 9명의 난쟁이 중에서 2명이 공주에게 거짓말하고 있습니다. 2명을 찾는 방법은 9명의 난쟁이들의 키를 모두 더한 값에서 2명씩 빼면서 그 결과가 100이 되는 경우를 찾으면 됩니다. [9명의 난쟁이들의 키의 합] - [거짓 난쟁이 후보 1] - [거짓 난쟁이 후보 2] = 100 소스 코드 #include #include #include using namespace std; int ..

문제 링크: https://www.acmicpc.net/problem/10448 10448번: 유레카 이론 문제 삼각수 Tn(n ≥ 1)는 [그림]에서와 같이 기하학적으로 일정한 모양의 규칙을 갖는 점들의 모음으로 표현될 수 있다. [그림] 자연수 n에 대해 n ≥ 1의 삼각수Tn는 명백한 공식이 있다. Tn = 1 + 2 + 3 + ... + n = n(n+1)/2 1796년, 가우스는 모든 자연수가 최대 3개의 삼각수의 합으로 표현될 수 있다고 증명하였다. 예를 들어, 4 = T1 + T2 5 = T1 + T1 + T2 6 = T2 + T2 or 6 = T www.acmicpc.net 문제 풀이 n의 크기가 1000밖에 되지 않기 때문에 모든 경우를 다 확인해보면 됩니다. 구하기에 앞서서, 50까지의..

문제 링크 : https://www.acmicpc.net/problem/2493 2493번: 탑 첫째 줄에 탑의 수를 나타내는 정수 N이 주어진다. N은 1 이상 500,000 이하이다. 둘째 줄에는 N개의 탑들의 높이가 직선상에 놓인 순서대로 하나의 빈칸을 사이에 두고 주어진다. 탑들의 높이는 1 이상 100,000,000 이하의 정수이다. www.acmicpc.net 문제 풀이 탑을 이중 포문을 돌려서 하나씩 확인하면 시간 초과로 문제를 풀지 못합니다. stack을 이용해서 O(N)으로 끝내버리는 것입니다. 문제의 예시를 보면, 6 9 5 7 4 4번의 탑은 왼쪽으로 송신을 보냈을 때, 수신을 받을 수 있는 탑은 7번입니다. 7번의 탑은 왼쪽으로 송신을 보냈을 때, 수신을 받을 수 있는 탑은 5번이 ..

문제 링크 : https://www.acmicpc.net/problem/1743 1743번: 음식물 피하기 문제 코레스코 콘도미니엄 8층은 학생들이 3끼의 식사를 해결하는 공간이다. 그러나 몇몇 비양심적인 학생들의 만행으로 음식물이 통로 중간 중간에 떨어져 있다. 이러한 음식물들은 근처에 있는 것끼리 뭉치게 돼서 큰 음식물 쓰레기가 된다. 이 문제를 출제한 선생님은 개인적으로 이러한 음식물을 실내화에 묻히는 것을 정말 진정으로 싫어한다. 참고로 우리가 구해야 할 답은 이 문제를 낸 조교를 맞추는 것이 아니다. 통로에 떨어진 음식물을 피해가기란 쉬운 일이 아 www.acmicpc.net 문제 풀이 DFS 알고리즘을 이용해서, 가장 큰 음식물의 크기를 구해주면 됩니다. 기존에 구한 음식물의 크기보다 더 큰 ..