분류 전체보기

[2872] 우리집엔 도서관이 있어(C++)

문제 바로가기 상근이는 컴퓨터 공학의 일인자가 되기 위해 책을 매우 많이 구매했다. 하지만, 집에 책장이 없어서 책을 탑처럼 쌓아놓고 있다. 오늘은 오랜만에 상근이가 집에서 휴식을 취하는 날이다. 상근이는 책을 알파벳 순서대로 정렬하려고 한다. 사전 순으로 가장 앞서는 책은 가장 위에 놓고, 가장 뒤에 있는 책은 가장 밑에 놓아야 한다. 책을 정렬할 때 사용할 수 있는 방법은 책 하나를 뺀 다음, 가장 위에 놓는 것이다. 책은 1부터 N까지 번호가 책 이름의 사전 순으로 매겨져 있다. 1은 사전 순으로 가장 앞서는 책이다. 따라서, 위에서부터 책의 번호를 읽으면 (1, 2, ..., N)이 되어야 한다. 예를 들어, 책이 3권있고 처음에 (3, 2, 1)로 쌓여있을 때, 2번 만에 사전순으로 책을 쌓을 ..

[1138] 한 줄로 서기

문제 1138번: 한 줄로 서기 첫째 줄에 사람의 수 N이 주어진다. N은 10보다 작거나 같은 자연수이다. 둘째 줄에는 키가 1인 사람부터 차례대로 자기보다 키가 큰 사람이 왼쪽에 몇 명이 있었는지 주어진다. i번째 수는 0보다 크거나 같고, N-i보다 작거나 같다. www.acmicpc.net 🔎 해결 방법 현재 상태에서 최선인 것만 보는 그리디 알고리즘을 사용해서 풀어야 하는 문제이기 때문에 말 그대로 모든 것을 현재 상황 기준으로 결정하면 된다. 예를 들어 줄을 서야 하는 사람의 수가 5명이고, 자신보다 왼쪽에 있는 사람 중 키 큰 사람의 수를 담고 있는 left배열이 다음과 같이 주어진다고 가정하자. 우선 키가 1인 사람부터 보면 1인 사람의 왼쪽에는 키가 1보다 큰 사람이 2명 있어야 한다. ..

[7568] 덩치(C++)

문제 7568번: 덩치 우리는 사람의 덩치를 키와 몸무게, 이 두 개의 값으로 표현하여 그 등수를 매겨보려고 한다. 어떤 사람의 몸무게가 x kg이고 키가 y cm라면 이 사람의 덩치는 (x,y)로 표시된다. 두 사람 A 와 B의 덩치가 각각 (x,y), (p,q)라고 할 때 x>p 그리고 y>q 이라면 우리는 A의 덩치가 B의 덩치보다 "더 크다"고 말한다. 예를 들어 어떤 A, B 두 사람의 덩치가 각각 (56,177), (45,165) 라고 한다면 A의 덩치가 B보다 큰 www.acmicpc.net 내 코드(C++) // [7568] 덩치 // https://www.acmicpc.net/problem/7568 #include #include #include using namespace std; in..

[11052] 카드 구매하기

https://www.acmicpc.net/problem/11052 11052번: 카드 구매하기 첫째 줄에 민규가 구매하려고 하는 카드의 개수 N이 주어진다. (1 ≤ N ≤ 1,000) 둘째 줄에는 Pi가 P1부터 PN까지 순서대로 주어진다. (1 ≤ Pi ≤ 10,000) www.acmicpc.net 🔎 해결 방법 예를 들어 민규가 구매하고자 하는 카드의 개수가 4개라면, 가능한 조합은 4 / 3 + 1 / 2 + 2 / 2 + 1 + 1 / 1 + 1 + 1 + 1 이므로 자연수의 분할로 접근하면 되는 줄 알았다. 그러면 각 경우는 위와 같이 계산하면 되는데 2 +2 가 문제였다. dp를 생각하지 못하고 2 + 2를 계속 p[2] + p[2]라고 계산하는 바람에 점화식을 세울 수 없었다. 하지만! ..

[2675] 문자열 반복

https://www.acmicpc.net/problem/2675 2675번: 문자열 반복 문제 문자열 S를 입력받은 후에, 각 문자를 R번 반복해 새 문자열 P를 만든 후 출력하는 프로그램을 작성하시오. 즉, 첫 번째 문자를 R번 반복하고, 두 번째 문자를 R번 반복하는 식으로 P를 만들면 된다. S에는 QR Code "alphanumeric" 문자만 들어있다. QR Code "alphanumeric" 문자는 0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ\$%*+-./: 이다. 입력 첫째 줄에 테스트 케이스의 개수 T(1 www.acmicpc.net 💡내 코드 Ver.1 (C) // [2675] 문자열 반복 // https://www.acmicpc.net/problem/2675 #i..

[5585] 거스름돈(C++)

문제 5585번: 거스름돈 문제 타로는 자주 JOI잡화점에서 물건을 산다. JOI잡화점에는 잔돈으로 500엔, 100엔, 50엔, 10엔, 5엔, 1엔이 충분히 있고, 언제나 거스름돈 개수가 가장 적게 잔돈을 준다. 타로가 JOI잡화점에서 물건을 사고 카운터에서 1000엔 지폐를 한장 냈을 때, 받을 잔돈에 포함된 잔돈의 개수를 구하는 프로그램을 작성하시오. 예를 들어 입력된 예1의 경우에는 아래 그림에서 처럼 4개를 출력해야 한다. 입력 입력은 한줄로 이루어져있고, 타로가 지불할 www.acmicpc.net 내 코드(C++) // [5585] 거스름돈 // https://www.acmicpc.net/problem/5585 #include using namespace std; int main(void) ..

[1003] 피보나치 함수(C++)

https://www.acmicpc.net/problem/1003 1003번: 피보나치 함수 각 테스트 케이스마다 0이 출력되는 횟수와 1이 출력되는 횟수를 공백으로 구분해서 출력한다. www.acmicpc.net 🔎 해결 방법 fibo(n) = fibo(n-1) + fibo(n-2) 인 것과 마찬가지로 0과 1이 출력되는 횟수도 이전의 두 개를 더해주면 된다. 즉, 점화식은 1. dp[n][0] = dp[n-1][0] + dp[n-2][0] 2. dp[n][1] = dp[n-1][1] + dp[n-2][1] 이렇게 두 가지를 사용하면 된다. 💡내 코드(C++) // [1003] 피보나치 함수 // https://www.acmicpc.net/problem/1003 #include using namespa..

[10844] 쉬운 계단 수

https://www.acmicpc.net/problem/10844 10844번: 쉬운 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 🔎 해결 방법 dp[1] = 9 dp[2] = 17 dp[3] = 32 dp[4] = 61 까지 찾고 점화식은 dp[i] = dp[i-1] * 2 - 1 이네! 하고 제출했는데 자꾸 틀렸다고 떠서 질문들을 찾아보니....전부 dp를 2차원으로 선언했길래 굳이 2차원까지 써야 돼? 나는 1차원으로 해결하겠어...라며....1차원으로 하다가... 결국 2차원으로 선언했다.ㅎㅎ 이건 가지치기로 나타내서 보면 이해하기가 쉬운데, 아래의 그림을 보자. 우선 이 문제에서 dp는 dp[길이][최고 자리 수] 로 정의했다. ..