Algorithm/Baekjoon Online Judge

    [java] 백준 2533 (사회망 서비스(SNS)) Gold 3
    Algorithm/Baekjoon Online Judge

    [java] 백준 2533 (사회망 서비스(SNS)) Gold 3

    문제 원문 링크 : https://www.acmicpc.net/problem/2533 2533번: 사회망 서비스(SNS) 페이스북, 트위터, 카카오톡과 같은 사회망 서비스(SNS)가 널리 사용됨에 따라, 사회망을 통하여 사람들이 어떻게 새로운 아이디어를 받아들이게 되는가를 이해하는 문제가 중요해졌다. 사회망 www.acmicpc.net Approach (Wrong) 내가 처음 생각했던 잘못된 접근법 처음에는 아무 노드나 루트로 잡고 level을 매겨서 min(홀수레벨 총 노드개수, 짝수레벨 총 노드개수)로 구현하면 될 줄 알았다. 질문 게시판에 있는 대부분의 반례 또한 통과되어 맞는 풀이법이라고 생각했으나, 다음과 같은 반례가 있었다. Approach (Correct) 자신이 얼리어답터인지, 아닌지 일때..

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

티스토리툴바