프로그래밍 diary

11057번 - 오르막 수 https://www.acmicpc.net/problem/11057 11057번: 오르막 수 오르막 수는 수의 자리가 오름차순을 이루는 수를 말한다. 이때, 인접한 수가 같아도 오름차순으로 친다. 예를 들어, 2234와 3678, 11119는 오르막 수이지만, 2232, 3676, 91111은 오르막 수가 아니다. 수 www.acmicpc.net 점화식: dp[i][j] = dp[i - 1][j] + dp[i][j - 1] 마지막 자리수의 값을 기준으로 문제를 풀었다. 3자리 숫자의 경우 003, 013, 113, 023, 123, 223, 033, 133, 233, 333 이렇게 총 10가지의 오르막 수로 구성된다. 바로 위의 풀이에서 볼 수 있듯이 마지막 수를 제외한 나머지..

12865번 - 평범한 배낭 https://www.acmicpc.net/problem/12865 12865번: 평범한 배낭 첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000) www.acmicpc.net dp 1 2 3 4 5 6 7 1 0 0 0 0 0 13 13 2 0 0 0 8 8 13 13 3 0 0 6 8 8 13 14 4 0 0 6 8 12 13 14 -> dp[N][K] dp[2][6]은 dp[1][6]와 dp[1][2] + 8을 비교하여 더 큰 값을 가져온 것이다. 여기서 2라는 인덱스 값..

1010번 - 다리 놓기 https://www.acmicpc.net/problem/1010 1010번: 다리 놓기 입력의 첫 줄에는 테스트 케이스의 개수 T가 주어진다. 그 다음 줄부터 각각의 테스트케이스에 대해 강의 서쪽과 동쪽에 있는 사이트의 개수 정수 N, M (0 < N ≤ M < 30)이 주어진다. www.acmicpc.net 점화식: dp[n][m] = dp[n][m - 1] + dp[n - 1][m - 1] n 값이 1일 때, 경우의 수는 m의 값을 따른다. n == m 일 때, 경우의 수는 1이다. 더보기 #include #define MAX 31 using namespace std; int T, N, M; long long dp[MAX][MAX] = {0, }; int site(int n..

2156번 - 포도주 시식 https://www.acmicpc.net/problem/2156 2156번: 포도주 시식 효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 같은 두 가지 규 www.acmicpc.net arr[] -> 문제에서 입력 받은 포도주의 용량을 저장 dp[][] -> 선택한 포도주 잔의 용량의 합을 저장 점화식 dp[0][i] = max(dp[1][i-1], dp[2][i-1]) + arr[i] dp[1][i] = max(dp[0][i-2], dp[1][i-2], dp[2][i-2]) + arr[i] dp[2][i] = max(dp[0][i-3], dp[1][i..

10844번 - 쉬운 계단 수 https://www.acmicpc.net/problem/10844 10844번: 쉬운 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net N = 1 1, 2, 3, 4, 5, 6, 7, 8, 9 N = 2 10, 12, 21, 23, 32, 34, 43, 45, 54, 56, 65, 67, 76, 78, 87, 89, 98 N = 3 101, 121, 123, 210, 212, 232, 234, 321, 323, 343, 345, 454, 456, 432, 434, 543, 545, 565, 567, 654, 656, 676, 678, 765, 767, 787, 789, 876, 878, 898, 987, 989 처..

1912번 - 연속합 https://www.acmicpc.net/problem/1912 1912번: 연속합 첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다. www.acmicpc.net 완성된 dp 배열에서 최댓값을 출력하면 문제에서 찾는 답이 된다. 점화식: dp[i] = dp[i] + dp[i-1], dp[i] = arr[i] 더보기 #include using namespace std; int n; int dp[100001] = { 0, }; int arr[100001] = { 0, }; int main() { cin >> n; for (int i = 1; i > ..

1699번 - 제곱수의 합 https://www.acmicpc.net/problem/1699 1699번: 제곱수의 합 어떤 자연수 N은 그보다 작거나 같은 제곱수들의 합으로 나타낼 수 있다. 예를 들어 11=32+12+12(3개 항)이다. 이런 표현방법은 여러 가지가 될 수 있는데, 11의 경우 11=22+22+12+12+12(5개 항)도 가능하다 www.acmicpc.net 점화식: dp[i] = dp[j * j] + dp[i - j * j] = 1 + dp[i - j * j] #include #include using namespace std; int N; int dp[100001] = { 0, }; int solution(int n) { //제곱근이 맞으면 0, 아니면 1 long long re; ..

10808번 - 알파벳 개수 BufferedReader를 사용하여 단어 S를 입력한다. 알파벳 개수를 나타낼 arr 배열을 선언한다. (길이는 알파벳 개수만큼!) 아스키코드를 사용하여 알파벳의 해당 인덱스를 1씩 더해준다. 마지막으로 반복문을 사용하여 append하고 sb를 출력한다. import java.io.*; public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringBuilder sb = new StringBuilder(); String S ..

11651번 - 좌표 정렬하기 2 입력받은 N에 따라 N개의 x, y좌표를 입력받기 위해 vetcor와 pair를 사용하였습니다. 입력받은 좌표를 문제 조건에 맞게 정렬하기 위해 sort를 사용하였습니다. sort()의 세 번째 인자에는 정렬의 기준이 되는 compare 함수(bool타입)를 입력하였습니다. compare 함수는 y좌표 값이 동일할 경우 x좌표 값을 비교하여 오름차순으로 정렬하고 동일하지 않을 경우 마찬가지로 오름차순으로 정렬하도록 구현하였습니다. #include #include #include using namespace std; bool compare(pairx, pairy) { if (x.second == y.second) return x.first < y.first; return ..

2292번 - 벌집 변수 cnt는 방의 번호, 변수 end는 cnt번방에 들어갈 수 있는 최대 숫자가 대입된다. 변수 num은 end의 범위를 증가시키기 위함이다. end를 1로 초기화(N==1 경우 무조건 1번 방이기 때문)하고, for문을 통해 end에 (6 * i)를 더해준다. 입력받은 N이 end를 넘지 않을 경우 cnt = 1 + i를 통해 방 번호를 저장하고 반복문을 종료한다. 입력받은 N이 end보다 클 경우 num += 2를 통해 end의 범위를 증가시킨다. 1번 방 : 1 (end1 = 1 + 6 * 0 = 1) 2번 방 : 2 ~ 7 (end2 = end1 + 6 * 1 = 7) 3번 방 : 8 ~ 19 (end3 = end2 + 6 * 2 = 19) 4번 방 : 20 ~ 37 (end..