나의 공부장

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