www.acmicpc.net/problem/2002 2002번: 추월 입력은 총 2N+1개의 줄로 이루어져 있다. 첫 줄에는 차의 대수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 대근이가 적은 차량 번호 목록이 주어지고, N+2째 줄부터 N개의 줄에는 영식이 www.acmicpc.net 백준 2002 추월 해당 문제는 map을 활용한 문제이다. map을 활용해 해당 표지판의 위치를 저장한 후 위치를 거스릴 때까지 체크 후 알맞은 포인트를 찾으면 방문했던 점을 제외하고 다음 위치를 찾아줍니다. 찾으려는 번호판의 숫자와 동일하다면 다음에 방문할 수 있는 점으로 이동해준다. 만약 현재 방문하려는 숫자와 틀린 경우 wrongNumber를 추가해주고 visit에 방문했음을 추가하여 맞았..

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

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를 출력하게된다. ..

백준 1563 개근상 www.acmicpc.net/problem/1563 1563번: 개근상 백준중학교에서는 학기가 끝날 무렵에 출결사항을 보고 개근상을 줄 것인지 말 것인지 결정한다. 이 학교는 이상해서 학생들이 학교를 너무 자주 빠지기 때문에, 개근상을 주는 조건이 조금 독 www.acmicpc.net 전형적인 dp문제이다. 이전의 정보를 이용해서 풀어야하는데 문제를 맞고나서 다른 사람들의 풀이를 보니 대부분 다르게 풀어서 내가 푼 방법을 공유하려고한다. 우선 3차원 배열을 이용해 dp[일][지각의 수][연속된 결석의 수]로 표현해주었다. 해당 일에 지각의 수와 연속된 결석의 수의 개근상이 가능한 사람의 수가 된다. 그럼 배열로 나타낼 수 있는 경우의 수는 얼마나 될까? dp[요일][0][0] = d..