www.acmicpc.net/problem/13707 13707번: 합분해 2 첫째 줄에 두 정수 N(1 ≤ N ≤ 5,000), K(1 ≤ K ≤ 5,000)가 주어진다. www.acmicpc.net 합분해 2 합분해는 몇개의 수 중에 몇개를 선택하여 N의 값을 만드는 문제이다. 여기서 골치아팠던 점은 앞뒤가 바뀌거나 중복되는 숫자가 나와도 되는 점이었다. 배열의 경우 의미하는 값은 dp[만들어야 하는 값][선택 개수]로 생각하고 풀었다. 여기서 dp 점화식을 어떻게 만들 수 있을까? 점화식에 앞서 N 까지의 수 중 선택하여 N을 만들 수 있는 방법은 몇개일까? 우선 dp[1][K]의 경우 K개가 된다. dp[1][1] = {1, } dp[1][2] = { {0, 1}, {1, 0} } dp[1][3..

www.acmicpc.net/problem/1937 1937번: 욕심쟁이 판다 n*n의 크기의 대나무 숲이 있다. 욕심쟁이 판다는 어떤 지역에서 대나무를 먹기 시작한다. 그리고 그 곳의 대나무를 다 먹어 치우면 상, 하, 좌, 우 중 한 곳으로 이동을 한다. 그리고 또 그곳에서 www.acmicpc.net 욕심쟁이 판다 문제는 dfs와 dp를 활용하여 해결하는 문제이다. 한번도 방문하지 않은 점에서만 시작하여 다시 되돌아가며 dp의 value를 업데이트 해준다. 또한 dfs상 모든 정점을 돌게 되면 시간 초과가 발생하기 때문에 dp를 활용하여 중복되는 점이면 바로 return 시켜주저야한다. dp 값을 -1로 초기화 후 다음 정점으로 갈때 마다 1씩 더해준다. 한번도 방문한 적이 없는 값이 면 0을 반환..

www.acmicpc.net/problem/1005 1005번: ACM Craft 첫째 줄에는 테스트케이스의 개수 T가 주어진다. 각 테스트 케이스는 다음과 같이 주어진다. 첫째 줄에 건물의 개수 N 과 건물간의 건설순서규칙의 총 개수 K이 주어진다. (건물의 번호는 1번부 www.acmicpc.net 1005번 위상정렬 위상 정렬이란 방향 그래프의 꼭짓점들의 방향을 거스리지 않고 정렬을 할 수 있는 알고리즘이다. 이 알고리즘은 dfs, stack와 queue를 활용하여 이러한 알고리즘을 해결 할 수 있다. stack으로 해결할 경우 각 정점이 어떤 위치에서 연결되었는지를 알 수 없어 이문제에서는 적당하지 못했다. 얘를 들어 아래와 같은 그래프가 있을 수 있다. 스택의 경우 반복문을 통해 비어있으면 df..

www.acmicpc.net/problem/1351 1351번: 무한 수열 첫째 줄에 3개의 정수 N, P, Q가 주어진다. www.acmicpc.net 이 문제는 dp유형이다. dp 배열을 map으로 만들어주어서 문제를 해결할 수 있었다. 왜 map을 사용했을까? 우선 입력값을 보면 10^12로 매우 크다 이를 배열로 표현하기에는 크게 무리가 있다고 생각했다. 그래서 나는 이 숫자들을 문자열로 만들어서 map의 키 값으로 지정하여 value를 저장하는 캐시를 만들어 주어 쉽게 해결할 수 있었다. 그 나머지는 조건 그대로 재귀를 구성해주면 된다. 더보기 #include #include #include using namespace std; #define ll long long map mp; ll getNu..

www.acmicpc.net/problem/1695 1695번: 팰린드롬 만들기 앞에서 뒤로 보나, 뒤에서 앞으로 보나 같은 수열을 팰린드롬 이라고 한다. 예를 들어 {1}, {1, 2, 1}, {1, 2, 2, 1}과 같은 수열은 팰린드롬 이지만, {1, 2, 3}, {1, 2, 3, 2} 등은 팰린드롬이 아니다. 한 수열 www.acmicpc.net 백준 1695 팰린드롬 만들기 팰린드롬이란 광고의 문구 앞뒤가 똑같은 전화번호와 똑같이 앞과 뒤가 같은 문자열을 뜻한다. 비슷한 문제로 이 문자열이 팰린드롬인지 판단하는 문제는 있었지만 이 문제의 경우 몇개의 숫자를 끼워 넣어야 팰린드롬이 되는지 맞추는 것이다. 우선 팰린드롬이 되는 규칙을 찾아야한다. 1 2 3 4 2 1, 2, 3, 4, 2의 경우 2..

www.acmicpc.net/problem/1707 1707번: 이분 그래프 입력은 여러 개의 테스트 케이스로 구성되어 있는데, 첫째 줄에 테스트 케이스의 개수 K(2≤K≤5)가 주어진다. 각 테스트 케이스의 첫째 줄에는 그래프의 정점의 개수 V(1≤V≤20,000)와 간선의 개수 www.acmicpc.net 백준 1707 이분 그래프 정답률이 꽤나 낮았는데 한번에 맞추어서 기분이 좋았던 문제이다. 백준 이분 그래프는 인접하지 않는 정점들을 두개의 그룹으로 나눌 수 있는지 판단하는 문제이다. 필자의 경우 현재의 그룹이 0이면 방문한적 있는 정점의 그룹이 현재 정점의 그룹과 같다면 NO를 출력해주었다. 오른쪽의 경우 4의 정점을 방문하고 있을 때 다음 정점의 3과 그룹이 같기 때문에 NO를 출력하게된다. ..