www.acmicpc.net/problem/2146 2146번: 다리 만들기 여러 섬으로 이루어진 나라가 있다. 이 나라의 대통령은 섬을 잇는 다리를 만들겠다는 공약으로 인기몰이를 해 당선될 수 있었다. 하지만 막상 대통령에 취임하자, 다리를 놓는다는 것이 아깝다 www.acmicpc.net 백준 2146 다리 만들기 다리 만들기 문제는 그래프 문제이며 최소 거리를 구하기 때문에 BFS를 사용하면 된다. 나는 이문제를 해결하는데 조금 비효율 적으로 해결해서 시간이 생각보다 많이 나왔다. 다른 풀이를 참고하셨으면 좋겠다. 다른 풀이도 풀고 싶지만 지금 내가 너무 피곤해서 내일 일어나서 적어야 겠다. 우선 단계적으로 1단계 각 섬을 분리하기 여기서는 BFS난 DFS 둘 중 아무거나 사용해도 된다. 2단계 각..

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/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..