벨로그로 바꿀까 고민하는 블로그

https://www.acmicpc.net/problem/11060 11060번: 점프 점프 재환이가 1×N 크기의 미로에 갇혀있다. 미로는 1×1 크기의 칸으로 이루어져 있고, 각 칸에는 정수가 하나 쓰여 있다. i번째 칸에 쓰여 있는 수를 Ai라고 했을 때, 재환이는 Ai이하만큼 오른쪽으로 www.acmicpc.net 점화식은 다음과 같다. dp[i + 1] = min(dp[i + 1], dp[i] + 1) ... dp[i + arr[i] - 1] = min(dp[i + arr[i], dp[i] + 1) dp[i + arr[i]] = min(dp[i +arr[i]], dp[i] + 1) dp배열은 1001으로 초기화 해주었다. 아무리 점프를 많이 해봤자 1001번 넘게 점프할 수는 없기 때문이다. H..

https://www.acmicpc.net/problem/17404 17404번: RGB거리 2 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 www.acmicpc.net 처음에는 이렇게 구현했는데 주어진 테스트케이스에서 첫번째 테스트케이스만 통과를 못했다. #include using namespace std; int main(void) { int n; int arr[3][1001]; int dp[3][1001]; int lastColor[3] = {0, 1, 2}; cin >> n; for (int i = 0; i < n; i++) {..

https://www.acmicpc.net/problem/13398 13398번: 연속합 2 첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다. www.acmicpc.net dp 배열을 이차원배열로 만들어서 연속합을 이루는 원소 중 하나가 없는 경우랑 그냥 연속합을 이루는 경우랑 나눠서 구하면 되는구나ㅠㅠㅠ 풀이를 보고 풀었는데 풀이랑 거의 똑같이 써서 제출했다ㅋㅋㅠㅠㅠ 참고 13398번 풀이: https://junbastick.tistory.com/8

https://www.acmicpc.net/problem/14002 14002번: 가장 긴 증가하는 부분 수열 4 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net solved.ac 잔디에 구멍 뚫렸길래 그냥 마음 편하게 시험공부나 하자 싶어서 며칠 안풀고 놀았더니 되게 오랜만에 푼 것 같다..ㅋㅋㅋㅋ 증가하는 부분 수열을 구하는 방법은 쉽게 떠올렸지만, 이걸 어떻게 역추적해서 출력해야할지 잘 감이 오지 않아서 풀이를 찾아봤다. HTML 삽입 미리보기할 수 없는 소스 dp[k]..

https://www.acmicpc.net/problem/1932 1932번: 정수 삼각형 첫째 줄에 삼각형의 크기 n(1 ≤ n ≤ 500)이 주어지고, 둘째 줄부터 n+1번째 줄까지 정수 삼각형이 주어진다. www.acmicpc.net 요즘 보안 과제 하느라고 백준 문제는 푸는 둥 마는 둥 하고 있다.. 잔디 비는게 싫어서 어떻게든 A+B 같은 쉬운 문제라도 매일 풀려고 하고 있긴한데 이게 무슨 의미가 있는건지 싶기도 하지만.. 왠지 한 번 해이해지면 그나마 하고 있던 알고리즘 공부조차 놓아버릴 것만 같은 생각이 들어서 시험기간이든 과제가 어렵든 상관없이 매일 한 문제라도 풀어야겠다는 고집을 부리고 있다... 이제 그래프스러운..? 문제를 보면 항상 재귀로 풀게 되는 것 같다. 알고리즘 교수님께서 재..

https://www.acmicpc.net/problem/2293 2293번: 동전 1 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. www.acmicpc.net 처음에는 이렇게 점화식을 세웠는데 dp[i] += dp[i - coins[j]] 중복이 아주 많이 나오기 때문에 계속 고민했다. 아무리 생각해봐도 점화식을 못세우겠어서 결국 풀이를 찾아봤다. 풀이를 이해한 바로는, 동전이 0원짜리 1개 있는 경우 동전이 0원짜리, 1원짜리 2개 있는 경우 ... 이렇게 동전의 개수를 늘려가면서 dp배열을 갱신해야 하는 것 같다. i == 6일 때 예를 들어보면 0원..

https://www.acmicpc.net/problem/2294 2294번: 동전 2첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. 가치가 같은 동전이 여러 번 주어www.acmicpc.net시간이 c++치고 엄청 오래걸린다. 배열을 안쓰고 벡터로 풀어서 그런건가?? 동전 문제는 그리디 알고리즘으로 최적해를 구할 수 있는 경우가 있고 없는 경우가 있다고 배웠는데, 까먹어서 Chat GPT한테 물어봤다. 동전 거스름돈 문제에서 동전의 단위가 서로 배수 관계가 아닐 경우 그리디 알고리즘은 최적해를 보장하지 못한다. *최적 부분 구조(optimal substruc..

https://www.acmicpc.net/problem/1520 1520번: 내리막 길 여행을 떠난 세준이는 지도를 하나 구하였다. 이 지도는 아래 그림과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다. 한 칸은 한 지점을 나타내는데 각 칸에는 그 지점의 높이가 쓰여 있으 www.acmicpc.net 0

https://www.acmicpc.net/problem/1890 1890번: 점프첫째 줄에 게임 판의 크기 N (4 ≤ N ≤ 100)이 주어진다. 그 다음 N개 줄에는 각 칸에 적혀져 있는 수가 N개씩 주어진다. 칸에 적혀있는 수는 0보다 크거나 같고, 9보다 작거나 같은 정수이며, 가장 www.acmicpc.net 포인터를 쓰거나 했다면 더 메모리를 적게 썼을지도 모르지만, 파이썬에 더 익숙해서 그런지 어떻게 풀어야 좋은 건지 잘 모르겠다.. 처음에는 반복문으로 풀었는데 (1, 1)에서 시작하는 경로의 개수만 셀 수가 없어서 결국 dfs처럼 풀었다. 근데 중간에 중복 처리를 안해서 시간 초과가 발생했다. 중복 처리를 안할 경우 답은 나오지만 지수 시간이 걸리기 때문에, 재방문을 하지 않도록 꼭 처리..

https://www.acmicpc.net/problem/11048 11048번: 이동하기 준규는 N×M 크기의 미로에 갇혀있다. 미로는 1×1크기의 방으로 나누어져 있고, 각 방에는 사탕이 놓여져 있다. 미로의 가장 왼쪽 윗 방은 (1, 1)이고, 가장 오른쪽 아랫 방은 (N, M)이다. 준규는 www.acmicpc.net 드디어 https://plzrun.tistory.com/entry/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EB%AC%B8%EC%A0%9C%ED%92%80%EC%9D%B4PS-%EC%8B%9C%EC%9E%91%ED%95%98%EA%B8%B0 이 글에 나왔던 백준 문제들을 (거의) 다 풀었다.. 플레만 빼고ㅋㅋ 거의 한 세달은 걸린 것 같다.. 이제 뭐할까 ..