백준 [1149] - kotlin

[문제] https://www.acmicpc.net/problem/1149 1149번: RGB거리 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 www.acmicpc.net [풀이] 문제의 조건은 다음과 같다. 1번 집의 색은 2번 집의 색과 같지 않아야 한다. N번 집의 색은 N-1번 집의 색과 같지 않아야 한다. i(2 ≤ i ≤ N-1)번 집의 색은 i-1번, i+1번 집의 색과 같지 않아야 한다. 결국 i번째는 i-1째 집의 색과 같지 않으면 된다. 예를 들어 i번째 색상이 빨강이라면, i -1번째는 파랑 또는 초록이 와야 한다...

• format_list_bulleted 백준/DP
• · 2023. 6. 25.
• textsms

백준 [3687] kotlin

[문제] https://www.acmicpc.net/problem/3687 3687번: 성냥개비 각 테스트 케이스에 대해서 입력으로 주어진 성냥개비를 모두 사용해서 만들 수 있는 가장 작은 수와 가장 큰 수를 출력한다. 두 숫자는 모두 양수이어야 하고, 숫자는 0으로 시작할 수 없다. www.acmicpc.net [풀이] 최대와 최소를 나누어 풀었다. [최대] 최대는 간단하다. 성냥개비를 2개를 사용하여 만들 수 있는 숫자는 1이다. 1개로 만들 수 있는 숫자는 없으므로, 임의의 숫자를 A라고 했을 때 A = (2 * n) + 3 으로 이루어져 있다고 볼 수 있다. 사용할 수 있는 성냥개비를 N이라고 하고, N을 2로 나누었을 때 몫을 a, 나머지를 b라고 하였을 때 1. a가 1이면 (N이 홀수인 경우..

• format_list_bulleted 백준/DP
• · 2023. 1. 16.
• textsms

백준 [1446] kotlin

[문제] https://www.acmicpc.net/problem/1446 1446번: 지름길 첫째 줄에 지름길의 개수 N과 고속도로의 길이 D가 주어진다. N은 12 이하인 양의 정수이고, D는 10,000보다 작거나 같은 자연수이다. 다음 N개의 줄에 지름길의 시작 위치, 도착 위치, 지름길의 길이 www.acmicpc.net [풀이] 지름길 배열을 우선순위 큐에 저정을 한다 (시작점 기준으로) 이동한 거리를 저장해두는 배열을 고속도로의 길이 D 크기만큼 생성해준다. 이때 초기값을 아래과 같이 설정해준다. var arr = IntArray(D+1){i -> i} 우선순위 큐에서 값을 하나씩 꺼내어서 값이 없을 때까지 다음 과정을 반복한다. 1. 끝에서 시작을 뺀 거리가 지름길의 거리보다 클 경우에 아..

• format_list_bulleted 백준/DP
• · 2023. 1. 12.
• textsms

백준 [15989] kotlin

[문제] https://www.acmicpc.net/problem/15989 15989번: 1, 2, 3 더하기 4 정수 4를 1, 2, 3의 합으로 나타내는 방법은 총 4가지가 있다. 합을 나타낼 때는 수를 1개 이상 사용해야 한다. 합을 이루고 있는 수의 순서만 다른 것은 같은 것으로 친다. 1+1+1+1 2+1+1 (1+1+2, 1+2+1) 2+2 www.acmicpc.net [풀이] 동전 교환 문제라고 볼 수 있다. 이 문제를 동전 교환 문제로 표현한다면, 1원,2원,3원으로 특정 금액 만드는 경우 수를 찾아야 한다. 문제에 만들어야 하는 수의 최대는 10000이므로, 0부터 10000까지 경우를 미리 찾아놓으면 된다. 동전 교환 알고리즘은 다음은 식으로 표현이 가능하다 . 비용을 저장해 놓은 배..

• format_list_bulleted 백준/DP
• · 2023. 1. 11.
• textsms

백준 14501 [kotlin]

문제 상담원으로 일하고 있는 백준이는 퇴사를 하려고 한다. 오늘부터 N+1일째 되는 날 퇴사를 하기 위해서, 남은 N일 동안 최대한 많은 상담을 하려고 한다. 백준이는 비서에게 최대한 많은 상담을 잡으라고 부탁을 했고, 비서는 하루에 하나씩 서로 다른 사람의 상담을 잡아놓았다. 각각의 상담은 상담을 완료하는데 걸리는 기간 Ti와 상담을 했을 때 받을 수 있는 금액 Pi로 이루어져 있다. N = 7인 경우에 다음과 같은 상담 일정표를 보자. 1일2일3일4일5일6일7일TiPi 3 5 1 1 2 4 2 10 20 10 20 15 40 200 1일에 잡혀있는 상담은 총 3일이 걸리며, 상담했을 때 받을 수 있는 금액은 10이다. 5일에 잡혀있는 상담은 총 2일이 걸리며, 받을 수 있는 금액은 15이다. 상담을 ..

• format_list_bulleted 백준/DP
• · 2022. 7. 22.
• textsms

백준 1309 [kotlin]

문제 어떤 동물원에 가로로 두칸 세로로 N칸인 아래와 같은 우리가 있다. 이 동물원에는 사자들이 살고 있는데 사자들을 우리에 가둘 때, 가로로도 세로로도 붙어 있게 배치할 수는 없다. 이 동물원 조련사는 사자들의 배치 문제 때문에 골머리를 앓고 있다. 동물원 조련사의 머리가 아프지 않도록 우리가 2*N 배열에 사자를 배치하는 경우의 수가 몇 가지인지를 알아내는 프로그램을 작성해 주도록 하자. 사자를 한 마리도 배치하지 않는 경우도 하나의 경우의 수로 친다고 가정한다. 입력 첫째 줄에 우리의 크기 N(1≤N≤100,000)이 주어진다. 출력 첫째 줄에 사자를 배치하는 경우의 수를 9901로 나눈 나머지를 출력하여라. 풀이 dp[i][j] 배열을 만든다. i는 0 1 2로 0은 왼쪽에 사자 1은 오른쪽 사자..

• format_list_bulleted 백준/DP
• · 2022. 7. 9.
• textsms