BOJ

    [java] 백준 15681 (트리와 쿼리) Gold 5
    Algorithm/Baekjoon Online Judge

    [java] 백준 15681 (트리와 쿼리) Gold 5

    문제 원문 링크 : https://www.acmicpc.net/problem/15681 15681번: 트리와 쿼리 트리의 정점의 수 N과 루트의 번호 R, 쿼리의 수 Q가 주어진다. (2 ≤ N ≤ 105, 1 ≤ R ≤ N, 1 ≤ Q ≤ 105) 이어 N-1줄에 걸쳐, U V의 형태로 트리에 속한 간선의 정보가 주어진다. (1 ≤ U, V ≤ N, U ≠ V) www.acmicpc.net Approach 트리에서의 DP문제다. 트리를 만들 때는 루트를 지정하고 시작하는 것이 편하다. 이 문제의 경우에는, 트리를 만들면서 배열에 자신의 서브노드 개수를 기록하면 된다. 함수를 재귀적으로 호출하면 Terminal Node부터 함수가 종료되기 때문에 쉽게 구현할 수 있다. Code import java.io..

    [java] 백준 17070 (파이프 옮기기 1) Gold 5
    Algorithm/Baekjoon Online Judge

    [java] 백준 17070 (파이프 옮기기 1) Gold 5

    문제 원문 링크 : https://www.acmicpc.net/problem/17070 17070번: 파이프 옮기기 1 유현이가 새 집으로 이사했다. 새 집의 크기는 N×N의 격자판으로 나타낼 수 있고, 1×1크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 (r, c)로 나타낼 수 있다. 여기서 r은 행의 번호, c는 열의 www.acmicpc.net Approach DP문제이다. 위 그림과 같이 파이프를 놓을 수 있고, 첫 파이프가 (1, 1) 과 (1, 2)를 차지할 수 있으므로 처음 놓을 수 있는 파이프는 3열부터 놓을수 있다. DP[i][j][1] = 파이프의 끝이 가로방향으로 (i, j) 에 놓여 있는 경우, DP[i][j][1] = DP[i][j - ..

    [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 : 연..

티스토리툴바