전체 글

[Baekjoon] 2565번 : 전깃줄

골드 5 2565번: 전깃줄 첫째 줄에는 두 전봇대 사이의 전깃줄의 개수가 주어진다. 전깃줄의 개수는 100 이하의 자연수이다. 둘째 줄부터 한 줄에 하나씩 전깃줄이 A전봇대와 연결되는 위치의 번호와 B전봇대와 연결되는 www.acmicpc.net 문제 풀이 전깃줄의 순서를 리스트로 입력받아 한쪽의 전기줄을 기준으로 정렬한다. 나머지 한쪽에 연결되는 전기줄의 번호가 증가하면 교차하지 않는다. 따라서 나머지 한쪽에 연결되는 번호들의 가장 긴 증가하는 수열을 찾고 전체 전기줄 수에서 빼면 삭제해야 할 전기줄의 최소 개수를 구할 수 있다. 코드 n = int(input()) nums = [] for i in range(n): nums.append(list(map(int, input().split()))) nu..

[Baekjoon] 11054번 : 가장 긴 바이토닉 부분 수열

골드 3 11054번: 가장 긴 바이토닉 부분 수열 첫째 줄에 수열 A의 크기 N이 주어지고, 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ N ≤ 1,000, 1 ≤ Ai ≤ 1,000) www.acmicpc.net 수열 S가 어떤 수 Sk를 기준으로 S1 Sk+1 > ... SN-1 > SN을 만족한다면, 그 수열을 바이토닉 수열이라고 한다. 예를 들어, {10, 20, 30, 25, 20}과 {10, 20, 30, 40}, {50, 40, 25, 10} 은 바이토닉 수열이지만, {1, 2, 3, 2, 1, 2, 3, 2, 1}과 {10, 20, 30, 40, 20, 30} 은 바이토닉 수열이 아니다. 수열 A가 주어졌을 때, 그 수열의 부분 ..

[Baekjoon] 2156번 : 포도주 시식

실버 1 2156번: 포도주 시식 효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 같은 두 가지 규 www.acmicpc.net 문제 풀이 이전 계단 오르기 문제와 비슷했다. 2022.01.20 - [Algorithm/Problem] - [Baekjoon] 2579번 : 계단 오르기 n 번째 와인을 먹는 경우는 한 칸 전의 와인을 먹는 경우(1)와 두칸 전의 와인을 먹는 경우(2)로 나뉜다. (1)번 경우는 n-3 와인까지의 최대 양에 n-1번째 와인의 양과 n번째 와인의 양을 더한 것이다. (2)번 경우는 n-2 와인까지의 최대 양에 n 번째 와인의 양을 더한 것이다. 여기까지는..

[Baekjoon] 1463번 : 1로 만들기

실버 3 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net 문제 풀이 세가지 경우에 대해 계산하고 최소값으로 보텀업하면 되는 문제 3으로 예를 들면 1) 1을 빼기 -> 2회 : 빼기 연산 1회 + 2를 1로 만드는 최소 연산횟수(1) 2) 2로 나누어 떨어지면 2로 나누기 -> 불가 (1e6) 3) 3으로 나누어 떨어지면 3으로 나누기 -> 1회 : 나누기 연산 1회 -> 이 세가지 경우 중 최소 값은 1회이다. 이를 코드로 나타내면 다음과 같다. 1) minus = dp[n-1] + 1 2) divide_3 = dp[n//3] + 1 (if n%3 == 0) 3) divide_2 = dp[n//2] + 1 (if n%2 ..