본문 바로가기

백준

[백준 BOJ] 1766 문제집 C++ 2020. 9. 23. [백준 BOJ] 1766 문제집 C++ 문제링크 : 백준 1766 문제집 1766번: 문제집 첫째 줄에 문제의 수 N(1 ≤ N ≤ 32,000)과 먼저 푸는 것이 좋은 문제에 대한 정보의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 둘째 줄부터 M개의 줄에 걸쳐 두 정수의 순서쌍 A,B가 빈칸을 사이에 두고 주 www.acmicpc.net 문제 민오는 1번부터 N번까지 총 N개의 문제로 되어 있는 문제집을 풀려고 한다. 문제는 난이도 순서로 출제되어 있다. 즉, 1번 문제가 가장 쉬운 문제이고 N번 문제가 가장 어려운 문제가 된다. 어떤 문제부터 풀까 고민하면서 문제를 훑어보던 민오는, 몇몇 문제들 사이에는 '먼저 푸는 것이 좋은 문제'가 있다는 것을 알게 되었다. 예를 들어 1번 문제를 풀고 ..
[백준 BOJ] 2252 줄 세우기 C++ 2020. 9. 22. [백준 BOJ] 2252 줄 세우기 C++ 문제링크 : 백준 2252 줄 세우기 2252번: 줄 세우기 첫째 줄에 N(1≤N≤32,000), M(1≤M≤100,000)이 주어진다. M은 키를 비교한 회수이다. 다음 M개의 줄에는 키를 비교한 두 학생의 번호 A, B가 주어진다. 이는 학생 A가 학생 B의 앞에 서야 한다는 의미이�� www.acmicpc.net 문제 N명의 학생들을 키 순서대로 줄을 세우려고 한다. 각 학생의 키를 직접 재서 정렬하면 간단하겠지만, 마땅한 방법이 없어서 두 학생의 키를 비교하는 방법을 사용하기로 하였다. 그나마도 모든 학생들을 다 비교해 본 것이 아니고, 일부 학생들의 키만을 비교해 보았다. 일부 학생들의 키를 비교한 결과가 주어졌을 때, 줄을 세우는 프로그램을 작성하시오..
[백준 BOJ] 9465 스티커 C++ 2020. 9. 2. [백준 BOJ] 9465 스티커 C++ 문제링크 : 백준 9465 스티커 9465번: 스티커 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 n (1 ≤ n ≤ 100,000)이 주어진다. 다음 두 줄에는 n개의 정수가 주어지며, 각 정수는 그 위치에 해당하는 스티커의 � www.acmicpc.net 문제 상근이의 여동생 상냥이는 문방구에서 스티커 2n개를 구매했다. 스티너느 그림 (a)와 같이 2행 n열로 배치되어 있다. 상냥이는 스티커를 이용해 책상을 꾸미려고 한다. 상냥이가 구매한 스티커의 품질은 매우 좋지 않다. 스티커 한 장을 떼면, 그 스티커와 변을 공유하는 스티커는 모두 찢어져서 사용할 수 없게 된다. 즉, 뗀 스티커의 왼쪽, 오른쪽, 위, 아래에 있는 스티커..
[백준 BOJ] 2294 동전 2 c++ 2020. 8. 31. [백준 BOJ] 2294 동전 2 c++ 문제 링크 : 백준 2294 동전 2 2294번: 동전 2 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. 가치가 같은 동전이 여러 번 주�� www.acmicpc.net 문제 n가지 종류의 동전이 있다. 이 동전들을 적당히 사용해서, 그 가치의 합이 k원이 되도록 하고 싶다. 그러면서 동전의 개수가 최소가 되도록 하려고 한다. 각각의 동전은 몇 개라도 사용할 수 있다. 사용한 동전의 구성이 같은데, 순서만 다른 것은 같은 경우이다. 입력 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,00..
[백준 BOJ] 2579 계단 오르기 C++ 2020. 8. 30. [백준 BOJ] 2579 계단 오르기 C++ 문제링크 : 백준 2579 계단 오르기 C++ 2579번: 계단 오르기 계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점 www.acmicpc.net 문제 계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점수를 얻게 된다. 예를 들어 와 같이 시작점에서부터 첫 번째, 두 번째, 네 번째, 여섯 번째 계단을 밟아 도착점에 도달하면 총 점수는 10 + 20 + 25 + 20 = 75점이 된다. 계단 오르는 데..
[백준 9095] 1, 2, 3 더하기 C++ 2020. 1. 15. 문제 링크 : 백준 9095 1, 2, 3 더하기 문제 정수 4를 1, 2, 3의 합으로 나타내는 방법은 총 7가지가 있다. 합을 나타낼 때는 수를 1개 이상 사용해야 한다. 1+1+1+1 1+1+2 1+2+1 2+1+1 2+2 1+3 3+1 정수 n이 주어졌을 때, n을 1, 2, 3의 합으로 나타내는 방법의 수를 구하는 프로그램을 작성하시오. 예시 입력 : 3 4 7 10 출력 : 7 44 274 풀이 직접 다 일일이 손으로 써가면서 만들어봐야 함. 그래서 규칙을 찾고 점화식으로 만들어서 풀면 됨. 내가 찾은 점화식은 f(n) = f(n-1) + f(n-2) + f(n-3) 이었음. 코드 #include #include using namespace std; int cache[11]; int main(..
[백준 11727] 2xn 타일링 2 c++ 2020. 1. 14. 문제 링크 : 백준 11727 2xn 타일링 2 문제 2xn 직사각형을 2x1과 2x2 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 예시 입력 : 2 / 출력 : 3 입력 : 8 / 출력 : 171 입력 : 12 / 출력 2731 풀이 직접 다 그려보면서 점화식을 찾았다. 점화식은 f(n) = (f(n-1) + f(n-2) * 2) 코드 #include #include using namespace std; #define MAX 1000 int cache[MAX]; int main() { int n; cin >> n; cache[1] = 1; cache[0] = 1; for(int i = 2; i
[백준 11726] 2xn 타일링 c++ 2020. 1. 8. 문제 링크 : 백준 11726 2xn 타일링 문제 2xn 크기의 직사각형을 1x2, 2x1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 예시 입력 : 2 / 출력 : 2 입력 : 9 / 출력 : 55 풀이 Bottom-up 방식의 DP. 규칙을 찾고 점화식을 세워 해결하는 방식이다. 그림을 그려보며 규칙을 찾아낸다. cache 배열에 3번째 인덱스까지의 값을 초기화 해준다. 내가 살짝 헤맸던 부분은 cache[i] 번째에 일단 i-1 번째 인덱스와 i-2번째 인덱스를 더해주고 나중에 답을 구할 때 10007 modulo 계산을 해주어 출력을 한 부분이 왜 오답인지 몰랐어서 헤맸다. 다시 생각해보니 반복문 안에서 modulo 연산을 해주지 않으면 이전 값이 전부 틀려버리기 때문에 반복문 안에서..

티스토리툴바