공대생 공부일지

[Silver II] 섬의 개수 - 4963문제 링크성능 요약메모리: 17272 KB, 시간: 152 ms분류그래프 이론, 그래프 탐색, 너비 우선 탐색, 깊이 우선 탐색제출 일자2024년 9월 15일 21:26:35문제 설명정사각형으로 이루어져 있는 섬과 바다 지도가 주어진다. 섬의 개수를 세는 프로그램을 작성하시오.한 정사각형과 가로, 세로 또는 대각선으로 연결되어 있는 사각형은 걸어갈 수 있는 사각형이다.두 정사각형이 같은 섬에 있으려면, 한 정사각형에서 다른 정사각형으로 걸어서 갈 수 있는 경로가 있어야 한다. 지도는 바다로 둘러싸여 있으며, 지도 밖으로 나갈 수 없다.입력입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 지도의 너비 w와 높이 h가 주어진다. w와..

[Gold V] 동전 1 - 2293문제 링크성능 요약메모리: 14288 KB, 시간: 112 ms분류다이나믹 프로그래밍제출 일자2024년 9월 14일 19:03:02문제 설명n가지 종류의 동전이 있다. 각각의 동전이 나타내는 가치는 다르다. 이 동전을 적당히 사용해서, 그 가치의 합이 k원이 되도록 하고 싶다. 그 경우의 수를 구하시오. 각각의 동전은 몇 개라도 사용할 수 있다.사용한 동전의 구성이 같은데, 순서만 다른 것은 같은 경우이다.입력첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다.출력첫째 줄에 경우의 수를 출력한다. 경우의 수는 231보다 작다.풀이..

[Silver I] 쉬운 계단 수 - 10844문제 링크성능 요약메모리: 14548 KB, 시간: 104 ms분류다이나믹 프로그래밍제출 일자2024년 9월 12일 17:04:03문제 설명45656이란 수를 보자.이 수는 인접한 모든 자리의 차이가 1이다. 이런 수를 계단 수라고 한다.N이 주어질 때, 길이가 N인 계단 수가 총 몇 개 있는지 구해보자. 0으로 시작하는 수는 계단수가 아니다.입력첫째 줄에 N이 주어진다. N은 1보다 크거나 같고, 100보다 작거나 같은 자연수이다.출력첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다.풀이재귀 바텀 업 방식으로 풀이하였다. 간단하게 재귀함수를 어떻게 구성할지 먼저 생각해보자. 1~9에 -1 과 +1을 해주며 재귀 함수를 호출하면 된다. 하..

[Gold V] 퇴사 2 - 15486문제 링크성능 요약메모리: 316340 KB, 시간: 652 ms분류다이나믹 프로그래밍제출 일자2024년 9월 11일 16:05:02문제 설명상담원으로 일하고 있는 백준이는 퇴사를 하려고 한다.오늘부터 N+1일째 되는 날 퇴사를 하기 위해서, 남은 N일 동안 최대한 많은 상담을 하려고 한다.백준이는 비서에게 최대한 많은 상담을 잡으라고 부탁을 했고, 비서는 하루에 하나씩 서로 다른 사람의 상담을 잡아놓았다.각각의 상담은 상담을 완료하는데 걸리는 기간 Ti와 상담을 했을 때 받을 수 있는 금액 Pi로 이루어져 있다.N = 7인 경우에 다음과 같은 상담 일정표를 보자.1일2일3일4일5일6일7일35112421020102015402001일에 잡혀있는 상담은 총 3일이 걸리며..

[Silver I] 포도주 시식 - 2156문제 링크성능 요약메모리: 16028 KB, 시간: 132 ms분류다이나믹 프로그래밍제출 일자2024년 9월 10일 14:26:41문제 설명효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 같은 두 가지 규칙이 있다.포도주 잔을 선택하면 그 잔에 들어있는 포도주는 모두 마셔야 하고, 마신 후에는 원래 위치에 다시 놓아야 한다.연속으로 놓여 있는 3잔을 모두 마실 수는 없다.효주는 될 수 있는 대로 많은 양의 포도주를 맛보기 위해서 어떤 포도주 잔을 선택해야 할지 고민하고 있다. 1부터 n까지의 번호가 붙어 있는 n개의 포도주 잔이 순서대로 ..

[Silver III] 이친수 - 2193문제 링크성능 요약메모리: 14456 KB, 시간: 100 ms분류다이나믹 프로그래밍제출 일자2024년 9월 9일 20:15:56문제 설명0과 1로만 이루어진 수를 이진수라 한다. 이러한 이진수 중 특별한 성질을 갖는 것들이 있는데, 이들을 이친수(pinary number)라 한다. 이친수는 다음의 성질을 만족한다.이친수는 0으로 시작하지 않는다.이친수에서는 1이 두 번 연속으로 나타나지 않는다. 즉, 11을 부분 문자열로 갖지 않는다.예를 들면 1, 10, 100, 101, 1000, 1001 등이 이친수가 된다. 하지만 0010101이나 101101은 각각 1, 2번 규칙에 위배되므로 이친수가 아니다.N(1 ≤ N ≤ 90)이 주어졌을 때, N자리 이친수의 개..

[Silver I] 스티커 - 9465문제 링크성능 요약메모리: 112500 KB, 시간: 600 ms분류다이나믹 프로그래밍제출 일자2024년 9월 7일 02:04:25문제 설명상근이의 여동생 상냥이는 문방구에서 스티커 2n개를 구매했다. 스티커는 그림 (a)와 같이 2행 n열로 배치되어 있다. 상냥이는 스티커를 이용해 책상을 꾸미려고 한다.상냥이가 구매한 스티커의 품질은 매우 좋지 않다. 스티커 한 장을 떼면, 그 스티커와 변을 공유하는 스티커는 모두 찢어져서 사용할 수 없게 된다. 즉, 뗀 스티커의 왼쪽, 오른쪽, 위, 아래에 있는 스티커는 사용할 수 없게 된다.모든 스티커를 붙일 수 없게된 상냥이는 각 스티커에 점수를 매기고, 점수의 합이 최대가 되게 스티커를 떼어내려고 한다. 먼저, 그림 (b)와..

[Silver II] 연속합 - 1912문제 링크성능 요약메모리: 23048 KB, 시간: 232 ms분류다이나믹 프로그래밍제출 일자2024년 9월 5일 17:44:34문제 설명n개의 정수로 이루어진 임의의 수열이 주어진다. 우리는 이 중 연속된 몇 개의 수를 선택해서 구할 수 있는 합 중 가장 큰 합을 구하려고 한다. 단, 수는 한 개 이상 선택해야 한다.예를 들어서 10, -4, 3, 1, 5, 6, -35, 12, 21, -1 이라는 수열이 주어졌다고 하자. 여기서 정답은 12+21인 33이 정답이 된다.입력첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다.출력첫째..

[Silver III] 조합 - 2407문제 링크성능 요약메모리: 14468 KB, 시간: 104 ms분류임의 정밀도 / 큰 수 연산, 조합론, 수학제출 일자2024년 9월 5일 03:27:13문제 설명nCm을 출력한다.입력n과 m이 주어진다. (5 ≤ n ≤ 100, 5 ≤ m ≤ 100, m ≤ n)출력nCm을 출력한다.풀이간단하게 조합을 구하는 구하는 문제다. 팩토리얼을 통해 구할 수도 있지만, 다이나믹 프로그래밍으로 풀어보겠다. 조합의 성질을 통해 nCr = n-1Cr + n-1Cr-1 이 된다. 참고로 32bit를 넘어가기 때문에 BigInteger를 사용해야 테스트케이스를 전부 통과할 수 있다.전체 코드public class Main { static int n=0,r=0; stati..

[Silver III] 2×n 타일링 2 - 11727문제 링크성능 요약메모리: 14380 KB, 시간: 104 ms분류다이나믹 프로그래밍제출 일자2024년 9월 3일 18:28:08문제 설명2×n 직사각형을 1×2, 2×1과 2×2 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오.아래 그림은 2×17 직사각형을 채운 한가지 예이다. 입력첫째 줄에 n이 주어진다. (1 ≤ n ≤ 1,000)출력첫째 줄에 2×n 크기의 직사각형을 채우는 방법의 수를 10,007로 나눈 나머지를 출력한다.풀이이전 포스트와 연결되는 문제이다.https://2junbeom.tistory.com/93 백준 11726번 2xn 타일링 (java)[Silver III] 2×n 타일링 - 11726문제 링크성능 요약메모리: 1..