본문 바로가기

해설35

[C/C++] 백준 17404: RGB 거리 2 https://www.acmicpc.net/problem/17404 17404번: RGB거리 2 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 www.acmicpc.net 하나 주의해야 할건 첫번째 칠한 집과 마지막으로 칠한 집의 색깔이 같으면 안되는것이다. 그렇기 때문에 기존의 DP로 문제를 풀게 된다면 이 조건을 만족시키기에 쉽지 않다. 따라서 여기서 생각해야하는건 첫번째로 칠할 집의 색깔을 정하고 나서 for문을 3번 돌며 각각의 경우세어 모든 집을 칠하는 비용의 최솟값을 구해야한다. 즉 dp[0][1]로 시작했을 때는 dp[1][.. 2023. 9. 28.
[C/C++] 백준 5639: 이진 검색 트리 (backtrack을 통한 후위순회) https://www.acmicpc.net/problem/5639 5639번: 이진 검색 트리 트리를 전위 순회한 결과가 주어진다. 노드에 들어있는 키의 값은 106보다 작은 양의 정수이다. 모든 값은 한 줄에 하나씩 주어지며, 노드의 수는 10,000개 이하이다. 같은 키를 가지는 노드는 없다 www.acmicpc.net 풀이!! 맨 처음에는 괄호를 이용한 후위 표기식 문제와 같이 stack에 넣음으로써 문제를 해결하려고 했지만 그렇게 할 경우 코드가 너무 복잡해지고 구현할 수가 없어 다른 방법을 모색하였다. 전위 순회의 특성상 루트-왼쪽 자식-오른쪽 자식 순으로 이동하기 때문에 전체의 루트를 하나만 잡았을 때 배열이 루트(1)-왼쪽자식 (n개)-오른쪽 자식(m)개가 된다. 예를 들어 50 30 24 .. 2023. 9. 26.
[C/C++] 백준 2206: 벽 부수고 이동하기 (BFS,tuple 이용 풀이) https://www.acmicpc.net/problem/2206 2206번: 벽 부수고 이동하기 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로 www.acmicpc.net 구현! 사실 원래의 BFS를 이용한 최단거리 알고리즘에서 조금만 추가하면 쉽게 풀 수 있는 문제이다. 여기서 중요한 것은 tuple안의 4개의 원소를 집어넣어 각각 x좌표, y좌표, 벽을 뚫고 지나갔는지에 대한 여부, 현재까지의 거리를 저장해야 하는 것이다. 또한 중요한 것이 visit 배열인데 기존의 2차원으로만 표현하면 안되고 3차원으로 표현하여 벽을 뚫고 지나갔는지에.. 2023. 9. 18.
[C/C++] 백준 11444: 피보나치 수 6 (점화식 풀이) https://www.acmicpc.net/problem/11444 11444번: 피보나치 수 6 첫째 줄에 n이 주어진다. n은 1,000,000,000,000,000,000보다 작거나 같은 자연수이다. www.acmicpc.net 맨 처음에 다른 문제처럼 DP로 풀려고 했지만 너무 범위가 커 메모리초과가 나왔다. 구현!! 이 문제와 같이 입력의 수가 과도하게 크고 DP를 사용해야할 상황일 때 (1.)항상 점화식을 2개로 나눠서 풀 수 있도록 생각을 해야한다. 특히 (2.)한번 지난간 곳을 저장해둬서 한번 지난 곳은 다시 못 지나가게 만들어 시간을 줄여야할 필요도 있다. 1) 그래서 점화식을 나누기 위해 머리를 굴렸지만 결국 두개로 나누지 못했다. 사실 거의 다 오긴 했지만 마지막에... 그렇게 다른 .. 2023. 9. 17.