0과 1의 쉼터

문제 7 3 8 8 1 0 2 7 4 44 5 2 6 5위 그림은 크기가 5인 정수 삼각형의 한 모습이다.맨 위층 7부터 시작해서 아래에 있는 수 중 하나를 선택하여 아래층으로 내려올 때, 이제까지 선택된 수의 합이 최대가 되는 경로를 구하는 프로그램을 작성하라. 아래층에 있는 수는 현재 층에서 선택된 수의 대각선 왼쪽 또는 대각선 오른쪽에 있는 것 중에서만 선택할 수 있다.삼각형의 크기는 1 이상 500 이하이다. 삼각형을 이루고 있는 각 수는 모두 정수이며, 범위는 0 이상 9999 이하이다.입력첫째 줄에 삼각형의 크기 n(1 ≤ n ≤ 500)이 주어지고, 둘째 줄부터 n+1번째 줄까지 정수 삼각형이 주어진다.출력첫째 줄에 합이 최대가..

풀이 n개의 정점에 대해 최단거리를 전부 구해준 후, 최단거리가 수색범위(m) 이하인 경우에 대해서 정점이 가지는 아이템의 합들의 최댓값을 구하면 된다. n개의 정점에 대해 최단거리를 구하기 위해 Floyd Warshall을 사용했다. n개의 정점에 대한 최단거리를 모두 구한 후, i번째 정점에서 출발해 수색범위 내로 이동할 수 있는 정점이 가지는 아이템의 합을 구하면 된다. n개의 정점에 대해 아이템 합의 최댓값을 출력해주면 된다. 소스코드 소스코드 보기 출처 14938번: 서강그라운드 예은이는 요즘 가장 인기가 있는 게임 서강그라운드를 즐기고 있다. 서강그라운드는 여러 지역중 하나의 지역에 낙하산을 타고 낙하하여, 그 지역에 떨어져 있는 아이템들을 이용해 서바이벌을 www.acmicpc.net

풀이 (0, 0)에서 (N - 1, M - 1)까지 최대 벽을 1개 부수며 도착할 수 있는 최단거리를 구하면 되는 문제다. 하나의 2차원 배열에 최단거리를 기록하기에는 어느 순간 벽을 부술때와 부수지 않는 경우 중 어떤 경우가 더 빨리 도달할지 기록하기 어렵다. 때문에 두 경우에 대해 최단거리를 기록하고, 가장 먼저 (N - 1, M - 1)에 도달한 경우의 최단거리를 출력해주면 된다. 2차원 배열을 벽을 부수는 경우와 부수지 않는 경우로 하지 않고, queue에 넣어줄 때 현재의 최단거리를 가지고 있는 Point객체를 넣어주는 방식으로 풀이했다. bfs를 진행하며 다음 영역이 벽이 아니라면, 벽을 부순경우와 부수지 않은 경우 모두 아무 제한 없이 queue에 넣어주면 된다. 만약 다음 영역이 벽이라면,..

풀이 문제에서 주어진 규칙에 따라 N줄을 내려가면서 최댓값과 최솟값을 구하면 되는 문제다. 주어진 규칙을 살펴보자. 별의 위치에 따라 더하거나 뺄수 있는 칸의 범위가 달라진다. 이번에는 아래 그림을 살벼보자 별이 기준이 아닌, 동그라미를 기준으로 각각 빨,초,파의 선을 그었다. 첫 번째 칸에 위치한 동그라미는 첫 번째와 두 번째의 별에 대해 더하거나 뺄 수 있다는 의미이다. 앞으로 계산해야되는 칸을 각각 max_dp, min_dp에 담아주자. 1번 줄은 그대로 담으면 된다. 2번 줄 부터 N번 줄까지는 위에서 말했듯 동그라미를 기준으로 계산하듯이 계산해주면 된다. 각각 max_dp와 min_dp를 구하는 코드이다. 코드가 너무 길다고 생각된다면 아래처럼 쌍으로 묶어주어 관리해도 된다. dp[0] = [ ..

풀이 가중치가 양수인 간선은 양방향, 음수인 간선은 단방향인 그래프에서 출발 정점에서 도착 정점까지 돌아오는 음수사이클이 존재하는지 확인하면 되는 문제다. 특이한 점이라 하면 출발점이 주어지지 않았고, 그래프 내에 어디든 상관없이 조건에 부합하는 음수 사이클이 존재하는지 여부만 알면 되는 문제다. 때문에 모든 정점을 출발점으로 간주하고 bellman ford를 여러 번 진행해야 한다. 만약 탐색 후 dist가 inf가 아니라면, 이미 탐색을 한 번 완료한 그래프이기에, 탐색이 되지 않은 또 다른 그래프에 대해서만 탐색을 진행해주었다. 좀 더 빠르게 탐색해보자. 어떤 정점을 기준으로 조건에 부합하는 음수 사이클이 존재하는지 모르기 때문에, 어차피 모든 정점에 대한 탐색이 이루어져야 하며 매 탐색마다 시작 ..

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

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

풀이 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