전체 글
[백준/1495/파이썬] 기타리스트
https://www.acmicpc.net/problem/1495 1495번: 기타리스트 첫째 줄에 N, S, M이 주어진다. (1 ≤ N ≤ 50, 1 ≤ M ≤ 1,000, 0 ≤ S ≤ M) 둘째 줄에는 각 곡이 시작하기 전에 줄 수 있는 볼륨의 차이가 주어진다. 이 값은 1보다 크거나 같고, M보다 작거나 같다. www.acmicpc.net Problem 곡의 개수 N과 시작 볼륨 S, 그리고 M이 주어졌을 때, 마지막 곡을 연주할 수 있는 볼륨 중 최댓값을 구하는 프로그램을 작성하시오. 조건 모든 곡은 리스트에 적힌 순서대로 연주해야 한다. 현재 볼륨이 P이고 지금 i번째 곡을 연주하기 전이라면, i번 곡은 P+V[i]나 P-V[i] 로 연주해야 한다. 하지만, 0보다 작은 값으로 볼륨을 바꾸거..
[백준/1720/파이썬] 타일코드
https://www.acmicpc.net/problem/1720 1720번: 타일 코드 2×N 크기의 넓은 판을 1×2 (또는 2×1) 크기와 2×2 크기의 타일로 채우려고 한다. 여러 가지 경우가 있을 수 있으므로, 각각을 하나의 코드로 대응시켜서 암호화에 이용하려고 한다. 그런데 문제가 www.acmicpc.net Problem N이 주어지면, 전체 타일 코드의 개수를 구하는 프로그램을 작성하시오. 조건 서로 좌우 대칭을 이루는 중복된 표현은 한 가지 경우로만 처리한다. 첫째 줄에 타일의 크기 N(1 ≤ N ≤ 30)이 주어진다. SOL "좌우 대칭을 이루는 중복된 표현"을 이해하기가 참 어려웠던 문제이다. 좌우대칭이라고 하면, 일반적으로 반을 딱 나눴을 때, 좌,우가 같으면 다 좌우대칭이라고 생각..
[백준/1309/파이썬] 동물원
https://www.acmicpc.net/problem/1309 1309번: 동물원 첫째 줄에 우리의 크기 N(1≤N≤100,000)이 주어진다. www.acmicpc.net Problem 동물원 조련사의 머리가 아프지 않도록 우리가 2*N 배열에 사자를 배치하는 경우의 수가 몇 가지인지를 알아내는 프로그램을 작성해 주도록 하자. 조건 이 동물원에는 사자들이 살고 있는데 사자들을 우리에 가둘 때, 가로로도 세로로도 붙어 있게 배치할 수는 없다. 이 동물원 조련사는 사자들의 배치 문제 때문에 골머리를 앓고 있다. 사자를 한 마리도 배치하지 않는 경우도 하나의 경우의 수로 친다고 가정한다. SOL 규칙성 발견하기 1부터 5까지 다 하고나서 알아낸 규칙입니다. 노가다 입니다. (진짜) F(n) = 2*F(n..
[백준/2240/파이썬] 자두나무
https://www.acmicpc.net/problem/2240 2240번: 자두나무 자두는 자두를 좋아한다. 그래서 집에 자두나무를 심어두고, 여기서 열리는 자두를 먹고는 한다. 하지만 자두는 키가 작아서 자두를 따먹지는 못하고, 자두가 떨어질 때까지 기다린 다음에 떨어 www.acmicpc.net Problem 매 초마다 어느 나무에서 자두가 떨어질지에 대한 정보가 주어졌을 때, 자두가 받을 수 있는 최대의 자두의 개수를 구해내는 프로그램을 작성하시오. 자두는 1번 자두나무 아래에 위치해 있다고 한다. 조건 자두는 키가 작아서 자두를 따먹지는 못하고, 자두가 떨어질 때까지 기다린 다음에 떨어지는 자두를 받아서 먹고는 한다. 자두를 잡을 때에는 자두가 허공에 있을 때 잡아야 하는데, 이는 자두가 말랑..
[백준/11066/파이썬] 파일 합치기
https://www.acmicpc.net/problem/11066 11066번: 파일 합치기 소설가인 김대전은 소설을 여러 장(chapter)으로 나누어 쓰는데, 각 장은 각각 다른 파일에 저장하곤 한다. 소설의 모든 장을 쓰고 나서는 각 장이 쓰여진 파일을 합쳐서 최종적으로 소설의 완성본 www.acmicpc.net Problem 소설의 각 장들이 수록되어 있는 파일의 크기가 주어졌을 때, 이 파일들을 하나의 파일로 합칠 때 필요한 최소비용을 계산하는 프로그램을 작성하시오. 조건 프로그램은 표준 입력에서 입력 데이터를 받는다. 프로그램의 입력은 T개의 테스트 데이터로 이루어져 있는데, T는 입력의 맨 첫 줄에 주어진다. 각 테스트 데이터는 두 개의 행으로 주어지는데, 첫 행에는 소설을 구성하는 장의 ..
[백준/11049/파이썬] 행렬 곱셈 순서
https://www.acmicpc.net/problem/11049 11049번: 행렬 곱셈 순서 첫째 줄에 입력으로 주어진 행렬을 곱하는데 필요한 곱셈 연산의 최솟값을 출력한다. 정답은 231-1 보다 작거나 같은 자연수이다. 또한, 최악의 순서로 연산해도 연산 횟수가 231-1보다 작거나 같 www.acmicpc.net Problem 행렬 N개의 크기가 주어졌을 때, 모든 행렬을 곱하는데 필요한 곱셈 연산 횟수의 최솟값을 구하는 프로그램을 작성하시오. 입력으로 주어진 행렬의 순서를 바꾸면 안 된다. 조건 첫째 줄에 행렬의 개수 N(1 ≤ N ≤ 500)이 주어진다. 둘째 줄부터 N개 줄에는 행렬의 크기 r과 c가 주어진다. (1 ≤ r, c ≤ 500) 항상 순서대로 곱셈을 할 수 있는 크기만 입력으..
[알고리즘,개념] 연쇄 행렬 곱셈 문제(CMM)
Chained Matrix Multiplication Problem 행렬의 곱셈에서, 행렬의 곱셈은 결합법칙이 성립한다. (A*B)*C = A*(B*C) 하지만, 행렬 곱셈의 순서에 따라서, 각 원소의 곱셈 횟수가 달라지게 된다. 예시) A=(5,2),B=(2,3),C=(3,6) AB *C : 5*2*3 +5*3*6 = 30+60 = 90 A*BC : 5*2*6+2*3*6 = 60+36 = 96 각 원소의 곱셈 횟수가 가장 작아지도록 하는 곱셈 순서를 구하고 싶다.(최적의 순서) Brute Force 하게 접근하기 모든 경우의 수에 대해서 계산하고,최적의 순서를 선택하면 된다. 예시를 하나씩 해보다보면 알겠지만, 이 문제는 다양하게 해석이 가능하다. 괄호를 씌울 수 있는 경우의 수 - (ABC)(D),(..
[백준/1520/파이썬] 내리막 길
https://www.acmicpc.net/problem/1520 1520번: 내리막 길 여행을 떠난 세준이는 지도를 하나 구하였다. 이 지도는 아래 그림과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다. 한 칸은 한 지점을 나타내는데 각 칸에는 그 지점의 높이가 쓰여 있으 www.acmicpc.net Problem 여행을 떠난 세준이는 지도를 하나 구하였다. 이 지도는 아래 그림과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다. 한 칸은 한 지점을 나타내는데 각 칸에는 그 지점의 높이가 쓰여 있으며, 각 지점 사이의 이동은 지도에서 상하좌우 이웃한 곳끼리만 가능하다. 지도가 주어질 때 이와 같이 제일 왼쪽 위 지점에서 출발하여 제일 오른쪽 아래 지점까지 항상 내리막길로만 이동하는 경로의 개수를 ..