0과 1의 쉼터

풀이 정수 n, h, v 입력받고, 길이가 n인 정사각형 케이크에서 각각 가로/세로로 h와 v에서 케이크를 잘라 4등분 할 때, 가장 부피가 큰 케이크의 부피를 풀력해주면 된다. 참고로 케이크의 높이는 4 이다. 가로/세로가 최댓값인 경우를 계산해주자. 소스코드 소스코드 보기 출처 17874번: Piece of Cake! The input consists of a single line containing three integers n (2 ≤ n ≤ 10 000), the length of the sides of the square cake in centimeters, h (0 < h < n), the distance of the horizontal cut from the top edge of the c..

풀이 스티커를 사용할 때 변을 공유하는 스티커는 사용할 수 없다는 조건이 있다. 따라서, 스티커를 최대한 많이 사용하고자 한다면 대각선으로 진행하며 사용할 때 가장 많은 스티커를 사용할 수 있다. 총 5개의 스티커를 고를 수 있다. 하지만, 이러한 방식이 항상 스티커 점수들의 최댓값임을 보장하지 않는다. 문제에서 주어진 경우를 살펴보자. 50 - 50 - 100 - 60 으로 총 4개의 스티커를 사용했지만, 스티커 점수들의 합은 260으로 이전에 선택한 경우보다 큰 점수를 가진다. 따라서, 각 스티커 영역마다 가질 수 있는 최댓값을 기록할 때 아래 그림과 같은 선택지를 고려해야 한다. 먼저, 단순하게 대각선으로 선택한 경우다. 주황색은 선택하지 못하는 영역, 초록색은 지금 선택한 영역, 파란색은 선택할 ..

풀이 입력받은 전화번호의 prefix number가 555이면 "YES"를, 아니면 "NO"를 출력하면 되는 문제이다. 소스코드 소스코드 보기 출처 17863번: FYI In the United States of America, telephone numbers within an area code consist of 7 digits: the prefix number is the first 3 digits and the line number is the last 4 digits. Traditionally, the 555 prefix number has been used to provide directory informatio www.acmicpc.net

풀이 LIS문제의 원리를 잘 다룬 문제이다. 기존에 O(N^2) 방식으로 LIS를 구할 때, 비연속 LIS 길이를 찾을 수 있었다. [백준 11053] 가장 긴 증가하는 부분 수열 [Python] 풀이 LIS (Longest Increasing Subsequence)는 최장 증가 부분 수열로, N개의 원소에 대해 요소를 골라 만든 부분 수열을 만들 때 각 원소가 이전 요소보다 큰 원소로 이루어진 부분 수열을 의미한다. 즉, 가 kyr-db.tistory.com LDS를 찾을 때도 마찬가지로 같은 방식을 사용했다. [백준 11722] 가장 긴 감소하는 부분 수열 [Python] 풀이 일전에 풀었던 LIS문제에서 사용한 방법을 응용해 풀이할 수 있다. [백준 11053] 가장 긴 증가하는 부분 수열 [Pyt..

풀이 일전에 풀었던 LIS문제에서 사용한 방법을 응용해 풀이할 수 있다. [백준 11053] 가장 긴 증가하는 부분 수열 [Python] 풀이 LIS (Longest Increasing Subsequence)는 최장 증가 부분 수열로, N개의 원소에 대해 요소를 골라 만든 부분 수열을 만들 때 각 원소가 이전 요소보다 큰 원소로 이루어진 부분 수열을 의미한다. 즉, 가 kyr-db.tistory.com LDS (Longest Decreasing Subsequence) 라고 하더라도, 결국은 LIS와 동일하게 요소간의 차이가 항상 커지거나 작아지는 비연속 부분 수열을 찾으면 되기 때문이다. 다만 주의할 점이 있는데, LIS의 길이를 구할 때 처럼 1번 요소부터 N번 요소 방향으로 탐색을 진행하면 기록되는 ..

풀이 LIS (Longest Increasing Subsequence)는 최장 증가 부분 수열로, N개의 원소에 대해 요소를 골라 만든 부분 수열을 만들 때 각 원소가 이전 요소보다 큰 원소로 이루어진 부분 수열을 의미한다. 즉, 가장 긴 비연속 부분 수열의 길이를 알아내면 된다. 그렇다면, LIS는 어떻게 만들어 지는가? 기본적으로 위에서 언급했 듯 이전 요소보다 큰 요소가 나오면 된다. 문제의 입력에서 알 수 있듯 항상 증가만 하는 요소로 주어지지 않는다. 아래 그림을 보자. 입력받은 배열 A와, 배열에 대한 LIS 길이를 기록할 dp배열이 있다. 그 아래에는 단순히 이전 요소보다 큰 요소가 나오는 경우만 기록한 Increasing Subsequence이다. 첫 번째 경우 10 - 20 - 30 - ..

풀이 combination을 구현해 값을 출력하면 되는 문제이다. 다른 언어의 경우 bigInteger가 없으면 구현하기 까다롭지만, Python에서는 표준 라이브러리를 이용해 풀이할 수 있다. 문제에서 주어지는 최댓값인 100 C 50은 작은 편으로 빨리 풀고 넘기자. 날먹 츄르릅.. 소스코드 소스코드 보기 출처 2407번: 조합 n과 m이 주어진다. (5 ≤ n ≤ 100, 5 ≤ m ≤ 100, m ≤ n) www.acmicpc.net

풀이 주어진 트리에 대해 트리의 지름을 구하면 되는 문제다. [백준 1967] 트리의 지름 [Python] 에서 더 많은 정점을 입력받는 동일한 문제이지만, 이전 글의 풀이와 동일한 방법으로 문제를 해결할 수 있다. 다른 점이라 하면, 입력이 양방향 그래프로 주어지기 때문에 따로 처리하지 않아도 된다. 소스코드 소스코드 보기 출처 1167번: 트리의 지름 트리가 입력으로 주어진다. 먼저 첫 번째 줄에서는 트리의 정점의 개수 V가 주어지고 (2 ≤ V ≤ 100,000)둘째 줄부터 V개의 줄에 걸쳐 간선의 정보가 다음과 같이 주어진다. 정점 번호는 1부터 V까지 www.acmicpc.net

풀이 주어진 트리에 대해 트리의 지름을 구하면 되는 문제다. 트리의 지름이란, 트리에서 임의의 두 정점을 연결하는 간선의 가중치 합이 최대가 되는 값을 의미한다. 즉, 문제에 나온 이미지처럼 임의의 두 정점을 길게 당길 때 가장 큰 원을 만들 수 있는 간선의 합이 트리의 지름을 의미한다. 그렇다면 임의의 두 정점을 연결하는 간선의 가중치 합이 최대가 되는 정점은 어떻게 찾을까? 임의의 두 정점(x, y)과 간선의 가중치의 합이 최대가 되는 정점(v1, v2)의 관계에 있어 다음과 같다. (x, y) 두 정점 모두 (v1, v2)와 일치할 때 : 한 번의 탐색으로 정답을 구할 수 있다. (x, y) 중 하나의 정점(x)만 (v1, v2)의 (v1)과 일치할 때 : 한 번의 탐색으로 (v1)를 구할 수 있다..

풀이 정수 N이 주어질 때, N^2의 최소 배수를 출력하면 된다. 즉, N^2 를 출력하면 된다. TC가 최대 20만개로 빠른 입력을 받자. 소스코드 소스코드 보기 출처 15372번: A Simple Problem. For each test case, output a single line containing the integer K, the answer for that test case. www.acmicpc.net