![]()
https://www.acmicpc.net/problem/11726 11726번: 2×n 타일링 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다. www.acmicpc.net 문제분석 코드 n = int(input()) a_1 = 1 a_2 = 1 for _ in range(2, n+1): temp = (a_1 + a_2) % 10007 a_1 = a_2 a_2 = temp print(a_2) 문제분석 1. n = 1일 때 1, 2일 때 1가지 방법으로 배치 가능하다. 2. n = 3일 때는 위의 n=1일때 가로길이 2짜리 블록을 배치하는 방법 + n=1일 때 가로 1짜리 블록을 배치하는 ..
https://www.acmicpc.net/problem/1895 1895번: 필터 숫자 9개가 오름차순이나 내림차순으로 정렬되어 있을 때, 중앙값은 다섯 번째 숫자이다. 예를 들어, 1, 3, 4, 1, 2, 6, 8, 4, 10의 중앙값은 4이다. (1 ≤ 1 ≤ 2 ≤ 3 ≤ 4 ≤ 4 ≤ 6 ≤ 8 ≤ 10) 이미지 I는 www.acmicpc.net 문제 분석 RxC 크기인 이미지 배열(=I)를 입력 받고, 3x3 배열의 필터를 씌여서 중앙값을 찾는 문제이다. 필 터를 씌어서 찾은 중앙값들을 정렬한 뒤, T 값 보다 큰 숫자들의 개수를 새는 문제이다. 코드 ㅋ 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29..
https://www.acmicpc.net/problem/17626 17626번: Four Squares 라그랑주는 1770년에 모든 자연수는 넷 혹은 그 이하의 제곱수의 합으로 표현할 수 있다고 증명하였다. 어떤 자연수는 복수의 방법으로 표현된다. 예를 들면, 26은 52과 12의 합이다; 또한 42 + 32 + 1 www.acmicpc.net 문제 분석 모든 자연수는 넷 혹은 그 이하의 제곱수의 합으로 표현할 수 있다고 증명하였다. 자연수 n이 주어질 때, n을 최소 개수의 제곱수 합으로 표현하는 문제이다. 조건. 입력은 자연수 n을 포함하는 한 줄로 구성된다. 1 ≤ n ≤ 50,000이다. 코드 다이나믹 프로그래밍 import math n = int(input()) dp = [0,1] for i ..
![]()
https://www.acmicpc.net/problem/1463 [문제해석] N을 입력하여 그 수가 위의 조건에 따라 1로 만드는 최소한의 횟수를 찾는 문제이다. [코드] n = int(input()) d = [0] * (n+1) for i in range(2, n+1) : d[i] = d[i-1] + 1 if i % 3 == 0 : d[i] = min(d[i], d[i//3]+1) if i % 2 == 0 : d[i] = min(d[i], d[i//2]+1) print(d[n]) [문제 풀이] n을 입력받는다. n+1 개수만큼의 0으로 된 리스트를 생성하고, 리스트 시작을 0번째가 아닌 첫번째로 시작하기 위해 n+1개로 설정한다. 입력된 값이 1이라면 어차피 계산횟수가 0이고, 그대로 출력하면 되..
문제 나코더 기장 재민이는 동아리 회식을 준비하기 위해서 장부를 관리하는 중이다. 재현이는 재민이를 도와서 돈을 관리하는 중인데, 애석하게도 항상 정신없는 재현이는 돈을 실수로 잘못 부르는 사고를 치기 일쑤였다. 재현이는 잘못된 수를 부를 때마다 0을 외쳐서, 가장 최근에 재민이가 쓴 수를 지우게 시킨다. 재민이는 이렇게 모든 수를 받아 적은 후 그 수의 합을 알고 싶어 한다. 재민이를 도와주자! 입력 첫 번째 줄에 정수 K가 주어진다. (1 ≤ K ≤ 100,000) 이후 K개의 줄에 정수가 1개씩 주어진다. 정수는 0에서 1,000,000 사이의 값을 가지며, 정수가 "0" 일 경우에는 가장 최근에 쓴 수를 지우고, 아닐 경우 해당 수를 쓴다. 정수가 "0"일 경우에 지울 수 있는 수가 있음을 보장할..
![]()
https://www.acmicpc.net/problem/6996 6996번: 애너그램 첫째 줄에 테스트 케이스의 개수(> n; for (int i = 0; i > str1 >> str2; if (str1.size() != str2.size()) { // 글자수 먼저 구별 cout
![]()
https://www.acmicpc.net/problem/1302 1302번: 베스트셀러 첫째 줄에 오늘 하루 동안 팔린 책의 개수 N이 주어진다. 이 값은 1,000보다 작거나 같은 자연수이다. 둘째부터 N개의 줄에 책의 제목이 입력으로 들어온다. 책의 제목의 길이는 50보다 작거나 같고 www.acmicpc.net 문제해석 책 이름을 n개만큼 입력 받고, 가장 많이 입력받은 책 이름을 출력하는 문제이다. 코드 #include #include #include #include using namespace std; int main(){ int Max =0; int n; cin >> n; map m; string str; for(int i=0;i> str; m[str]++; } for (int i= m.be..
![]()
백준 1149 RGB거리 Intro Solution 주어진 규칙 중 세 번째 규칙이 앞의 두 규칙을 모두 포함하는 말이다. 연속으로 같은 색깔을 색깔을 선택할 수 없으므로, 색깔별로 나누어 누적 비용을 저장한다. n번째 집에서 빨강을 선택할 때는 n-1번째 집에서 초록을 선택할 경우의 비용의 누적 합과 파랑을 선택할 경우의 비용의 누적 합을 비교하여 최솟값을 찾아 더하면 된다. 예를 들어 입력이 다음과 같다고 해보자. 입력 3 26 40 83 49 60 57 13 89 99 그러면 비용의 누적 합은 다음과 같은 순서로 저장된다. ''' dp[1] = [26, 40, 83] dp[2] = [49+min(40, 83), 60+min(26, 83), 57+min(26, 40)] = [89, 86, 83] dp..
![]()
https://www.acmicpc.net/problem/7579 7579번: 앱 입력은 3줄로 이루어져 있다. 첫 줄에는 정수 N과 M이 공백문자로 구분되어 주어지며, 둘째 줄과 셋째 줄에는 각각 N개의 정수가 공백문자로 구분되어 주어진다. 둘째 줄의 N개의 정수는 현재 활 www.acmicpc.net 문제 분석 새로운 앱을 활성화하기 위해서 기존에 활성화 된 앱들을 종료해 메모리를 확보하는 문제입니다. 앱을 종료할 때 고려할 사항으로는 앱이 차지하는 메모리와 앱을 종료했을 때 발생하는 비용이 있습니다. 새로운 앱을 활성화 할 수 있을 만큼 충분한 메모리를 확보하면서 비용은 최소화하는 것이 목적입니다. 일종의 배낭 문제로, 다이나믹 프로그래밍을 활용해 문제를 해결할 수 있습니다. 얼핏 보기에 메모리가 ..
![]()
https://www.acmicpc.net/problem/1463 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net 문제분석 분류 DP(동적계획법) 문제설명 입력받은 수를 최소한의 연산으로 1로 만들기 연산은 3종류 x-1 if(x % 3 == 0), x / 3 if(x % 5 == 0), x / 5 동적계획법 Bottom-up 방식으로 진행 입력 10 출력 3 코드 #include #include #include using namespace std; vectordp; int main() { int n; cin >> n; dp.assign(n+1,-1); dp[1] = 0; for (int x = 2; x
![]()
https://www.acmicpc.net/problem/1520 1520번: 내리막 길 여행을 떠난 세준이는 지도를 하나 구하였다. 이 지도는 아래 그림과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다. 한 칸은 한 지점을 나타내는데 각 칸에는 그 지점의 높이가 쓰여 있으 www.acmicpc.net 문제분석 현재 자신이 있는 위치보다 낮은 위치로 갈 수 있고 0,0 에서 n-1,m-1까지 갈 수 있는 경로의 개수를 구하는 문제이다. 코드 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.Arrays; import java.util.StringTokeni..
![]()
https://www.acmicpc.net/problem/9012 9012번: 괄호 괄호 문자열(Parenthesis String, PS)은 두 개의 괄호 기호인 ‘(’ 와 ‘)’ 만으로 구성되어 있는 문자열이다. 그 중에서 괄호의 모양이 바르게 구성된 문자열을 올바른 괄호 문자열(Valid PS, VPS)이라고 www.acmicpc.net 문제분석 1) '('의 개수와 ')'의 개수가 같은지 파악 2) 개수는 같지만 ')'가 먼저 입력될 경우 3) 끝날 때 '('로 끝나는 경우 문제풀이 - '('과 ')'의 짝이 맞는지 '('가 나오면 +1, ')'가 나오면 -1을 하는 count 선언 - 만약 ')'가 먼저 나오는 경우 count가 음수로 가기 때문에 음수로 가는 경우가 있는지 변수 t를 통해서 저장..
