전체 글

[BOJ/Python] 구간 합 구하기 5 || 다이나믹 프로그래밍

백준 구간 합 구하기 5 11660 11660번: 구간 합 구하기 5첫째 줄에 표의 크기 N과 합을 구해야 하는 횟수 M이 주어진다. (1 ≤ N ≤ 1024, 1 ≤ M ≤ 100,000) 둘째 줄부터 N개의 줄에는 표에 채워져 있는 수가 1행부터 차례대로 주어진다. 다음 M개의 줄에는 네 www.acmicpc.net더보기❏ 문제 설명❍ 문제N×N개의 수가 N×N 크기의 표에 채워져 있다. (x1, y1)부터 (x2, y2)까지 합을 구하는 프로그램을 작성하시오. (x, y)는 x행 y열을 의미한다.예를 들어, N = 4이고, 표가 아래와 같이 채워져 있는 경우를 살펴보자.234534564567여기서 (2, 2)부터 (3, 4)까지 합을 구하면 3+4+5+4+5+6 = 27이고, (4, 4)부터 (4,..

[BOJ/Python] 평범한 배낭 || 다이나믹 프로그래밍

백준 평범한 배낭 파이썬 12865 12865번: 평범한 배낭 첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000) www.acmicpc.net 더보기 ❏ 문제 설명 ❍ 문제 이 문제는 아주 평범한 배낭에 관한 문제이다. 한 달 후면 국가의 부름을 받게 되는 준서는 여행을 가려고 한다. 세상과의 단절을 슬퍼하며 최대한 즐기기 위한 여행이기 때문에, 가지고 다닐 배낭 또한 최대한 가치 있게 싸려고 한다. 준서가 여행에 필요하다고 생각하는 N개의 물건이 있다. 각 물건은 무게 W와 가치 V를 가지는데, 해당 ..

[BOJ/Python] 점프 || 다이나믹 프로그래밍

백준 점프 파이썬 1890 1890번: 점프 첫째 줄에 게임 판의 크기 N (4 ≤ N ≤ 100)이 주어진다. 그 다음 N개 줄에는 각 칸에 적혀져 있는 수가 N개씩 주어진다. 칸에 적혀있는 수는 0보다 크거나 같고, 9보다 작거나 같은 정수이며, 가장 www.acmicpc.net 더보기 ❏ 문제 설명 ❍ 문제 N×N 게임판에 수가 적혀져 있다. 이 게임의 목표는 가장 왼쪽 위 칸에서 가장 오른쪽 아래 칸으로 규칙에 맞게 점프를 해서 가는 것이다. 각 칸에 적혀있는 수는 현재 칸에서 갈 수 있는 거리를 의미한다. 반드시 오른쪽이나 아래쪽으로만 이동해야 한다. 0은 더 이상 진행을 막는 종착점이며, 항상 현재 칸에 적혀있는 수만큼 오른쪽이나 아래로 가야 한다. 한 번 점프를 할 때, 방향을 바꾸면 안 된..

[Goorm/Python] 발전기 (2) || 구름톤 챌린지 (DFS, BFS)

구름톤 챌린지 발전기 (2) 파이썬 구름LEVEL 난이도별 다양한 문제를 해결함으로써 SW 역량을 향상시킬 수 있습니다. level.goorm.io 더보기 ❏ 문제 설명 ❍ 문제 구름 심시티를 하고 있는 플레이어는 한 변의 길이가 N인 정사각형 모양의 마을 M을 만들고 있다. 마을의 모든 칸에는 건물이 하나씩 있고, r번째 행, c번째 열에 해당하는 칸에는 정수 $M_{r, c}$가 적혀 있다. $M_{r, c}$는 해당 칸에 있는 건물의 유형의 번호를 의미한다. 건물의 유형이 동일하면서, 서로 상하좌우 인접한 칸에 위치한 건물끼리는 서로 전력을 공유할 수 있다. 전력을 공유할 수 있는 관계에 속한 건물의 개수가 K개 이상이면 이를 단지라고 한다. 플레이어는 발전기를 설치해 각 단지에 전력을 공급하고자 ..

[Goorm/Python] 발전기 || 구름톤 챌린지 (DFS, BFS)

구름톤 챌린지 발전기 파이썬 구름LEVEL 난이도별 다양한 문제를 해결함으로써 SW 역량을 향상시킬 수 있습니다. level.goorm.io 더보기 ❍ 문제 구름 심시티를 하고 있는 플레이어는 한 변의 길이가 N인 정사각형 모양의 마을 M을 만들고 있다. r번째 행, c번째 열에 해당하는 칸에는 숫자 $M_{r, c}$가 적혀 있다. $M_{r, c}$는 0 또는 1 중 하나이며, 각 숫자가 의미하는 바는 아래와 같다. 0이면 아무것도 없는 칸이다. 1이면 집이 있는 칸이다. 마을에 있는 집에 전력을 공급하기 위해선 그 집에 발전기를 설치하거나, 상하좌우로 인접한 집 중 하나가 전력을 공급받고 있으면 된다. 플레이어가 모든 집에 전력을 공급하기 위해서 설치해야 할 발전기의 최소 개수를 구해보자. ❍ 입력..

[Goorm/Python] 통증 (2) || 구름톤 챌린지 (다이나믹 프로그래밍)

구름톤 챌린지 통증(2) 파이썬 구름LEVEL 난이도별 다양한 문제를 해결함으로써 SW 역량을 향상시킬 수 있습니다. level.goorm.io 더보기 ❏ 문제 풀이 ❍ 문제 구름-그라운드 게임에는 통증이라는 시스템이 있다. 통증 수치가 높다면 게임에서 승리하기 어려워지므로, 아이템을 적절히 사용해 통증 수치를 0으로 유지하는 것이 중요하다. 게임 안에는 통증 수치를 감소시켜 주는 아이템이 2종류가 있다. 아이템의 이름은 A, B이고, 각 아이템을 사용 시 각각 $A_p, B_p$만큼 통증 수치를 감소시켜 준다. 각 아이템은 원하는 만큼 획득할 수 있다. 플레이어는 적과의 전투에서 피해를 입어 현재 N의 통증 수치를 가지고 있다. 플레이어가 통증 수치를 0으로 줄이기 위해 필요한 아이템의 최소 개수를 구..

[Goorm/Python] GameJam || 구름톤 챌린지 (런타임에러)

구름톤챌린지 GameJam 파이썬 195692 구름LEVEL 난이도별 다양한 문제를 해결함으로써 SW 역량을 향상시킬 수 있습니다. level.goorm.io 더보기 ❍ 문제 플레이어는 GameJam에 참가했다. GameJam은 현장에서 즉석으로 팀을 꾸려 게임의 규칙을 만든 뒤, 생각한 규칙을 코드로 옮겨서 게임을 만들어내는 대회이다. 플레이어가 속한 팀은 보드로 즐길 수 있는 간단한 보드게임을 만들었다. 게임의 진행 방법과 규칙은 다음과 같다. 게임은 한 변의 길이가 N인 격자 보드 위에서 진행한다. 보드는 한 변의 길이가 1인 $N^2$개의 칸으로 나누어져 있다. 각 칸에는 에 해당하는 방향으로 칸만큼 한 칸씩 이동하라는 지시가 적혀있다. 플레이하는 사람은 처음에 보드의 칸 중 하나에 말을 올려놓는..

[Goorm/Python] 문자열 나누기 || 구름톤 챌린지

구름톤 챌린지 문자열 나누기 195688 파이썬 구름LEVEL 난이도별 다양한 문제를 해결함으로써 SW 역량을 향상시킬 수 있습니다. level.goorm.io 더보기 ❍ 문제 길이가 N인 문자열 S가 주어진다. 플레이어는 문자열 S를 서로 겹치지 않는 3개의 부분 문자열로 나누려고 한다. 부분 문자열은 모두 길이가 1 이상이어야 하며, 원래 문자열에서 연속해야 한다. 문자열을 나누는 방법에 따라 플레이어는 점수를 얻을 수 있다. 점수는 다음 과정에 따라 계산된다. 문자열 S를 위 조건에 따라 나눴을 때, 등장하는 모든 부분 문자열을 중복 제거하고 사전순으로 정렬한 결과를 P라고 한다. 나누어진 3개의 문자열이 각각 P에서 i, j, k번째로 등장하는 문자열이라면, 얻을 수 있는 점수는 i + j + k..

[구름톤 챌린지/Python] Day 4 - 완벽한 햄버거 만들기

구름톤 챌린지 완벽한 햄버거 만들기 파이썬 구름LEVEL난이도별 다양한 문제를 해결함으로써 SW 역량을 향상시킬 수 있습니다.level.goorm.io더보기❍ 문제구름 햄버거는 다양한 재료를 사용하여 만들어서 맛있기로 유명하다. 구름 햄버거는 N개의 재료를 순서대로 쌓아서 만들고, 구름 햄버거의 맛은 사용된 모든 재료의 맛의 정도를 더한 값이다.완벽한 구름 햄버거를 만들기 위해서는 맛의 정도가 가장 높은 재료를 기준으로 위랑 아래로 갈 수록 재료의 맛의 정도가 감소하거나 같아야 한다.플레이어는 N개의 재료를 순서대로 쌓아서 구름 햄버거를 하나 만들었다. i번째로 쌓은 재료의 맛의 정도가 $k_i$라고 할 때, 플레이어가 만든 구름 햄버거의 맛을 구해보자.만약 플레이어가 완벽하지 않은 구름 햄버거를 만들었..

[구름톤 챌린지/Python] Day 2 - 프로젝트 매니징

구름톤 챌린지 프로젝트 매니징 파이썬 구름LEVEL난이도별 다양한 문제를 해결함으로써 SW 역량을 향상시킬 수 있습니다.level.goorm.io더보기❍ 문제플레이어는 구름 프로젝트의 일정을 관리하는 PM(프로젝트 매니저)이자 유일한 개발자다. 현재 구름 프로젝트를 완수하기 위해서는 N개의 기능 개발이 추가로 필요하다. 각 기능에는 1번부터 N번까지 번호가 붙어 있고, i번째 기능을 개발하는데는 $c_i$분의 시간이 걸린다.플레이어는 프로젝트를 기한 안에 끝내기 위해 철야 작업에 들어갔다. 플레이어가 철야 작업을 시작한 시간은 T시 M분이다. 플레이어는 1번 기능부터 순서대로 개발을 진행하고, 한 기능 개발을 끝마치면 바로 다음 기능의 개발을 시작한다. 플레이어가 모든 기능 개발을 끝마친 시각을 구해보자..