본문 바로가기

전체 글

 (201)
[BOJ 1449] 수리공 항승(C++) https://www.acmicpc.net/problem/1449 1449번: 수리공 항승 첫째 줄에 물이 새는 곳의 개수 N과 테이프의 길이 L이 주어진다. 둘째 줄에는 물이 새는 곳의 위치가 주어진다. N과 L은 1,000보다 작거나 같은 자연수이고, 물이 새는 곳의 위치는 1,000보다 작거나 www.acmicpc.net 물이 새는 곳을 다 막을 수 있는 테이프의 최소 개수를 알아봐야 한다. 구멍난 곳부터 시작해서 막는 것이 더 많은 범위를 커버할 수 있다. (그리디 알고리즘) 해설코드(C++). 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 #include #include #in..
[BOJ 2437] 저울(C++, 자세한 설명) https://www.acmicpc.net/problem/2437 2437번: 저울 하나의 양팔 저울을 이용하여 물건의 무게를 측정하려고 한다. 이 저울의 양 팔의 끝에는 물건이나 추를 올려놓는 접시가 달려 있고, 양팔의 길이는 같다. 또한, 저울의 한쪽에는 저울추들만 놓� www.acmicpc.net 해설코드(C++). 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 #include #include #include using namespace std; vector v; int val, next = 0, N; int main() { cin >> N; for(int i = 1; i > val; v.push_back(val); ..
[BOJ 1783] 병든 나이트(C++) https://www.acmicpc.net/problem/1783 1783번: 병든 나이트 첫째 줄에 체스판의 세로 길이 N와 가로 길이 M이 주어진다. N과 M은 2,000,000,000보다 작거나 같은 자연수이다. www.acmicpc.net 이 문제는 체스가 위와 아래로 움직일 때, 항상 오른쪽으로 간다. 다양한 케이스를 코드로 구현하면 되는 문제이다. 해설코드(C++). 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 #include using namespace std; long long N, M; long long answer = 1; int main() { cin >> N >> M; if(N >= 3){ if(M ..
[BOJ 1138] 한 줄로 서기(C++). https://www.acmicpc.net/problem/1138 1138번: 한 줄로 서기 첫째 줄에 사람의 수 N이 주어진다. N은 10보다 작거나 같은 자연수이다. 둘째 줄에는 키가 1인 사람부터 차례대로 자기보다 키가 큰 사람이 왼쪽에 몇 명이 있었는지 주어진다. i번째 수는 0보다 � www.acmicpc.net N번째 사람부터 놓기 시작하면, 현재의 상황만 보고 순서를 고려하면 된다.(그리디) i번째를 놓을 때, i + 1번째부터 N까지 놓아졌다면 모든 수는 i보다 크므로, 아래의 코드를 작성할 수 있다. 해설코드(C++). 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35..
[BOJ 2624] 동전 바꿔주기(C++, 다이나믹 프로그래밍) https://www.acmicpc.net/problem/2624 2624번: 동전 바꿔주기 명보네 동네 가게의 현금 출납기에는 k 가지 동전이 각각 n1, n2, … , nk개 씩 들어있다. 가게 주인은 명보에게 T원의 지폐를 동전으로 바꿔 주려고 한다. 이때, 동전 교환 방법은 여러 가지가 있을 www.acmicpc.net 해설코드(C++). 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 #include #include #include using namespace std; int T, k; int dp[..
[BOJ 1072] 게임(C++) https://www.acmicpc.net/problem/1072 1072번: 게임 각 줄에 X와 Y가 주어진다. X는 1,000,000,000보다 작거나 같은 자연수이고, Y는 0보다 크거나 같고, X보다 작거나 같은 자연수이다. www.acmicpc.net 게임 기록은 다음과 같이 생겼다. 게임 횟수 : X 이긴 게임 : Y (Z %) Z는 형택이의 승률이다. 소수점은 버린다. 예를 들어, X=53, Y=47이라면, Z = 88이다. X와 Y가 주어졌을 때, 형택이가 게임을 몇 판 더해야 Z가 변하는지 구하는 프로그램을 작성하시오. 몇 판을 더하는 횟수를 a라고 하면, (X + a) / (Y + a) >= (X / Y) + (1 / 100) 을 구하기 위해선, 양변에 Y를 곱해야 하는데, Y의 최댓값..
[BOJ 1080] 행렬(C++) https://www.acmicpc.net/problem/1080 1080번: 행렬 첫째 줄에 행렬의 크기 N M이 주어진다. N과 M은 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 행렬 A가 주어지고, 그 다음줄부터 N개의 줄에는 행렬 B가 주어진다. www.acmicpc.net "0과 1로만 이루어진 행렬 A와 행렬 B가 있다. 이때, 행렬 A를 행렬 B로 바꾸는데 필요한 연산의 횟수의 최솟값을 구하는 프로그램을 작성하시오." A 행렬을 B 행렬로 만든다는 것은, 값이 다른 행렬의 원소들을 모두 바꿔야하는 것을 의미한다. 이중 For문을 이용해 순차적으로 값이 다른 행렬의 원소들을 바꾸면서 정답을 찾을 수 있을까? 값이 다른 원소들을 임의의 순서로 골라서 바꿔야지 연산 횟수의 최솟값을..
[BOJ 1049] 기타줄 https://www.acmicpc.net/problem/1049 1049번: 기타줄 첫째 줄에 N과 M이 주어진다. N은 100보다 작거나 같은 자연수이고, M은 50보다 작거나 같은 자연수이다. 둘째 줄부터 M개의 줄에는 각 브랜드의 패키지 가격과 낱개의 가격이 공백으로 구분하여 주 www.acmicpc.net "끊어진 기타줄의 개수 N과 기타줄 브랜드 M개가 주어지고, 각각의 브랜드에서 파는 기타줄 6개가 들어있는 패키지의 가격, 낱개로 살 때의 가격이 주어질 때, 적어도 N개를 사기 위해 필요한 돈의 수를 최소로 하는 프로그램을 작성하시오." 가장 최소의 금액으로, 끊어진 기타줄을 고칠 수 있는 방법을 찾아야 한다. 그러기 위해서 필요한 것은, 가장 싼 패키지 가격, 가장 싼 낱개 가격을 이용해야..

티스토리툴바