본문 바로가기

분류 전체보기

 (248)
[C++] 백준 15990번 : 1, 2, 3 더하기 5 (S3) #문제 www.acmicpc.net/problem/15990 15990번: 1, 2, 3 더하기 5 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 1,000,000,009로 나눈 나머지를 출력한다. www.acmicpc.net #풀이 & 학습한 내용 중복이 안 되게 해야 하므로 마지막이 어떤 수인지에 대해 구분을 하여 경우의 수를 저장해주어야 한다. 2차원 배열을 선언하여 마지막에 더해지는 수 1, 2, 3에 대해 그 인덱스에 맞는 곳에 경우의 수를 저장한다. 인덱스를 0부터 해도 되지만 마침 마지막에 더해지는 수가 1 ,2, 3이므로 편하게 인덱스 또한 1,2,3일 때에 해당되도록 해서 헷갈리는 일이 없게 했다. #소스코드 1 2 3 4 5 6 7 8 9 10 11 12 13..
[C++] 백준 11052번 : 카드 구매하기 (S1) & 16194번 : 카드 구매하기 2 (S1) #문제 www.acmicpc.net/problem/11052 11052번: 카드 구매하기 첫째 줄에 민규가 구매하려고 하는 카드의 개수 N이 주어진다. (1 ≤ N ≤ 1,000) 둘째 줄에는 Pi가 P1부터 PN까지 순서대로 주어진다. (1 ≤ Pi ≤ 10,000) www.acmicpc.net www.acmicpc.net/problem/16194 16194번: 카드 구매하기 2 첫째 줄에 민규가 구매하려고 하는 카드의 개수 N이 주어진다. (1 ≤ N ≤ 1,000) 둘째 줄에는 Pi가 P1부터 PN까지 순서대로 주어진다. (1 ≤ Pi ≤ 10,000) www.acmicpc.net #풀이 & 학습한 내용 마지막에 뽑는게 몇 장짜리 팩인지에 대해 접근했다. 직접 예시를 손으로 써가며 dp에 활용할 수..
Lecture 10: Object-Oriented Programming (4) - interface 안에 variable을 구현하면 기본적으로 public static final이다. - interface 안에 구현할 수 있는 method들은 abstract, static, default, private(섞어서 가능)이다. 앞에 아무것도 없으면 기본이 public, abstract다. Static method: Interface안에서 구현까지 한다. 호출은 반드시 Interface이름으로 한다. (cf. factory method) Default method: Interface안에서 구현까지 하고, override가능하다. override없으면 Interface안 구현으로 호출된다. (2개 이상 interface를 implement하고 같은 이름, 같은 인자의 default메소드 ..
[C++] 백준 15988번 : 1, 2, 3 더하기 3 (S2) #문제 www.acmicpc.net/problem/15988 15988번: 1, 2, 3 더하기 3 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 1,000,000,009로 나눈 나머지를 출력한다. www.acmicpc.net #풀이 & 학습한 내용 int 범위의 최대는 2,147,483,647이다. 대략 2,000,000,000으로 기억해두자. 문제에서 dp배열을 int로 선언하면, dp[i - 1] + dp[i - 2] + dp[i - 3]을 계산할 때, int범위의 최댓값을 벗어날 수 있다. 따라서 dp배열을 long long으로 선언해야 한다. 모듈로 연산의 성질인 (A + B)%C = (A%C + B%C)%C도 기억해두자. 이때, (A%C + B)%C도 가능하다는 점도..
[C++] 백준 9095번 : 1, 2, 3 더하기 (S3) #문제 www.acmicpc.net/problem/9095 9095번: 1, 2, 3 더하기 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다. www.acmicpc.net #풀이 & 학습한 내용 마지막에 올 수 있는 수는 1,2,3 중 하나이다. 그리고 마지막 수를 빼면 같은 문제로 문제의 크기만 n-1, n-2, n-3이 되므로 dp를 이용한다. 이때 dp배열의 초깃값으로 dp[1]=1, dp[2]=2, dp[3]=4를 넣어주고 반복문으로 dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3]을 통해 dp[10]까지 계산한다. #소스코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 #inclu..
[C++] 백준 11727번 : 2×n 타일링 2(S3) #문제 www.acmicpc.net/problem/11727 11727번: 2×n 타일링 2 2×n 직사각형을 1×2, 2×1과 2×2 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×17 직사각형을 채운 한가지 예이다. www.acmicpc.net #풀이 & 학습한 내용 기존 2×n 타일링 문제에서 마지막에 올 수 있는 경우가 하나 추가된 문제이다. 타일의 마지막은 2x1타일 하나, 1X2타일 2개, 2X2타일 1개가 가능하다. 각각에 따른 문제는 같은 문제로 사이즈만 n-1, n-2, n-2일때와 같다. dp배열의 초기값으로 n=1일 때 1, n=2일 때 3을 넣어줬다. 그리고 dp[i] = (dp[i - 1] + 2 * dp[i - 2])를 통해 for문으로 순차적으로 dp..
[C++] 백준 11726번 : 2×n 타일링 (S3) #문제 www.acmicpc.net/problem/11726 11726번: 2×n 타일링 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다. www.acmicpc.net #풀이 & 학습한 내용 마지막에 타일이 올수 있는 경우는 1개가 서있는것과, 2개가 가로로 누워있는 것이다. 각각의 경우는 n-1과 n-2일 때의 문제를 푸는 것과 동일하므로 dp를 이용하여 앞에서부터 순차적으로 n까지 dp배열을 채워나간다. 이때 dp의 basis case는 n=1일 때 1과 n=2일 때 2이다. 또한, 문제에서 무언가로 나눈 답을 구하란 것을 문제를 푸는 과정에서 나누면서 구하라는 뜻이다. #소스코드 1 ..
[C++] 백준 1463번 : 1로 만들기 (S3) #문제 www.acmicpc.net/problem/1463 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net #풀이 & 학습한 내용 우선 최솟값을 구할 때 #include 의 min에 {}로 대소 비교할 값들을 묶어서 전달하여 최솟값을 구했다. 또한, dp를 이용할 때 먼저 basis case로 숫자가 2와 3일 때의 dp배열에 1 값을 넣었으며, 이후에는 for문을 통해 N까지 순차적으로 계산하였다. 이때, 경우는 2와 3으로 모두 나누어 떨어질 때, 2로만 나누어 떨어질 때, 3으로만 나누어 떨어질 때, 2와 3 모두로 나누어 떨어지지 않을 때로 나누었다. 연산의 횟수이므로 이전의 optimization에 1을 더해주어 ..

티스토리툴바