백준

[14501] 퇴사(C++)

🍃 문제 바로가기 🔎 해결 방법 처음에는 앞에서부터 계산을 하려고 했었다. 예를 들어, dp[n] 을 n일까지 상담을 했을 때 얻을 수 있는 최대 이익이라고 한다면 가능한 모든 경우를 조합해서 그 중 max 값을 찾아서 dp에 저장하려고 했는데 이렇게 하다보니 예외 처리 해줘야 할 것이 너무 많아서 결국 구글링의 도움을 받았다. 첫째날부터 계산을 해도 풀 수 있긴 하지만, 마지막 날 부터 계산을 한다면 코드도 간결하고 훨씬 더 간단하게 답을 도출할 수 있다! 만약 위와 같은 표가 주어졌다면, 1. dp[7] 7 + t[7] = 9 > 8 이므로 7일에 있는 상담은 할 수 없다. 따라서 dp[7] = dp[8] = 0 (dp[n + 1] = 0으로 사전에 초기화 해줘야 함) 2. dp[6] 6 + t[6]..

[4963] 섬의 개수(C++)

문제 정사각형으로 이루어져 있는 섬과 바다 지도가 주어진다. 섬의 개수를 세는 프로그램을 작성하시오. 한 정사각형과 가로, 세로 또는 대각선으로 연결되어 있는 사각형은 걸어갈 수 있는 사각형이다. 두 정사각형이 같은 섬에 있으려면, 한 정사각형에서 다른 정사각형으로 걸어서 갈 수 있는 경로가 있어야 한다. 지도는 바다로 둘러싸여 있으며, 지도 밖으로 나갈 수 없다. 입력 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 지도의 너비 w와 높이 h가 주어진다. w와 h는 50보다 작거나 같은 양의 정수이다. 둘째 줄부터 h개 줄에는 지도가 주어진다. 1은 땅, 0은 바다이다. 입력의 마지막 줄에는 0이 두 개 주어진다. 출력 각 테스트 케이스에 대해서, 섬의 개수를 출력한다..

[2512] 예산

문제 2512번: 예산 첫째 줄에는 지방의 수를 의미하는 정수 N이 주어진다. N은 3 이상 10,000 이하이다. 다음 줄에는 각 지방의 예산요청을 표현하는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 값들은 모두 1 이상 100,000 이하이다. 그 다음 줄에는 총 예산을 나타내는 정수 M이 주어진다. M은 N 이상 1,000,000,000 이하이다. www.acmicpc.net 처음엔 코드도 60줄이 넘고 내가 생각하기에도 코드가 너무 복잡한 것 같은데 제출 결과도 계속 틀렸다고 떠서 뭐가 문제일까 생각해봤더니 예외 테스트케이스가 있었다... 이분 탐색 문제였기 때문에 자꾸만 어떤 표본들의 중간값을 찾으려고 했던 탓이다. 예를 들어, 각 지방에서 요청한 예산이 100, 110, 120, 130 ..

[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..