Algorithm

    [java] 백준 17404 (RGB거리 2) Gold 4
    Algorithm/Baekjoon Online Judge

    [java] 백준 17404 (RGB거리 2) Gold 4

    문제 원문 링크: https://www.acmicpc.net/problem/17404 17404번: RGB거리 2 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 www.acmicpc.net 비슷한 문제 백준 1149 (RGB거리) Silver 1 1149번: RGB거리 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 www.acmicpc.net Approach DP문제이다..

    [java] 백준 1149 (RGB거리) Silver 1
    Algorithm/Baekjoon Online Judge

    [java] 백준 1149 (RGB거리) Silver 1

    문제 원문 링크: https://www.acmicpc.net/problem/1149 1149번: RGB거리 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 www.acmicpc.net Approach DP문제이다. DP[i][j] = i번째 집을 j색으로 칠했을 때의 최소비용값이라 할 때, Min(DP[N][빨강], DP[N][초록], DP[N][파랑]) 을 구하면 되는 문제이다. 연속된 집을 같은 색깔로 칠할 수는 없으므로 밑의 점화식을 적용시킬 수 있다. DP[i][j] = Min(DP[i - 1][(j + 1) % 3], DP[i -..

    [java] 백준 12852 (1로 만들기 2) Silver 1
    Algorithm/Baekjoon Online Judge

    [java] 백준 12852 (1로 만들기 2) Silver 1

    문제 원문 링크: https://www.acmicpc.net/problem/12852 Approach DP 문제이다.DP[i] = i를 만들 수 있는 최소 연산 수. 라고 하였을 때,i 를 만들 수 있는 가짓 수는 다음 3가지이다. 이 중 최소 연산 수를 DP[i]에 저장하면 된다. i - 1 숫자에서 +1 을 하여 i를 만드는 경우 i / 2 숫자에서 *2 를 하여 i를 만드는 경우 i / 3 숫자에서 *3 을 하여 i를 만드는 경우위의 규칙으로 밑의 점화식을 도출할 수 있다. DP[i] = min(DP[i - 1], DP[i / 2], DP[i / 3]) 위의 식은 Bottom-up 방식의 점화식이다.i가 2나 3으로 나누어 떨어질 경우에만 나눠야 하므로 위의 식에 조건을 추가하여야 한다.추가로 N을..

    [java] 백준 14888 (연산자 끼워넣기) Silver 1
    Algorithm/Baekjoon Online Judge

    [java] 백준 14888 (연산자 끼워넣기) Silver 1

    문제 원문 링크: https://www.acmicpc.net/problem/14888 14888번: 연산자 끼워넣기 첫째 줄에 수의 개수 N(2 ≤ N ≤ 11)가 주어진다. 둘째 줄에는 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 100) 셋째 줄에는 합이 N-1인 4개의 정수가 주어지는데, 차례대로 덧셈(+)의 개수, 뺄셈(-)의 개수, www.acmicpc.net Approach Backtracking 기법을 사용하여 모든 연산자의 모든 조합을 고려하는 BruteForce 문제이다. 연산자를 하나씩 늘려가며 값을 구해나가고 연산자를 다 사용하였을 때의 값이 최댓값/최솟값인지를 판별한다. 사용한 후 남은 연산자의 개수가 몇개 인지를 기록하여야 한다. Code /* no.14888 : 연..

티스토리툴바