판교의 메타몽

문제 링크 HackerRank : Davis' Staircase (Click) 문제 요약 Davis의 집에는 계단이 많은데, Davis는 한번에 계단을 오를때 1칸, 2칸, 또는 3칸을 오를 수 있다. Davis가 n층 높이의 계단을 오를때, 몇 가지의 가지수로 계단을 오를 수 있는지 정답을 구하라. 이때 정답은 10000000007로 나눈 나머지를 출력하라. 문제 풀이 public static int stepPerms(int n) { if(n == 0) return 0; else if(n == 1) return 1; else if(n == 2) return 3; else if(n == 3) return 4; int t1 = 1; int t2 = 2; int t3 = 4; int res = 0; ..

24392번: 영재의 징검다리 첫 줄에 N과 M(1 ≤ N, M ≤ 1,000)이 공백으로 구분되어 주어지고, 그 뒤에는 N줄에 걸쳐 다리의 정보가 주어진다. 강화유리의 경우 1, 일반 유리의 경우 0으로 주어진다. www.acmicpc.net 문제 요약 1. 첫 줄에 N과 M, 영재가 건널 수 있는 다리 정보 N*M (1 h >> w; for(int i=0; i arr[i][j]; } } int main() { input(); for(int i=0; i=0; i--){ for(int j=0; j

문제 링크 : https://www.acmicpc.net/problem/1446 1446번: 지름길 첫째 줄에 지름길의 개수 N과 고속도로의 길이 D가 주어진다. N은 12 이하이고, D는 10,000보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에 지름길의 시작 위치, 도착 위치, 지름길의 길이가 주 www.acmicpc.net 문제 요약 1. 세준이는 0에서 D킬로미터 길이의 고속도로를 지나 학교를 간다. 2. N개의 지름길 정보가 주어진다. 3. 세준이가 학교에 가기 위해 운전해야 하는 거리의 최솟값을 구해라. 4. 단, 모든 길은 일방통행이고 고속도로를 역주행할 수는 없다. 핵심 포인트 이 문제에서 주의해야할 점은 문제 요약의 4번입니다. 모든 길은 일방통행이고 고속도로를 역주행할 수는 없다..

문제 링크 : https://www.acmicpc.net/problem/10942 10942번: 팰린드롬? 총 M개의 줄에 걸쳐 홍준이의 질문에 대한 명우의 답을 입력으로 주어진 순서에 따라서 출력한다. 팰린드롬인 경우에는 1, 아닌 경우에는 0을 출력한다. www.acmicpc.net 문제 요약 1. 팰린드롬(Palindrome)은 '회문'입니다. 예를들어 '스위스', '11011'처럼 뒤집어도 의미가 똑같은 단어를 뜻합니다. 2. 수열 n의 크기, 수열 n을 입력 받은 뒤, 테스트 케이스 m과 m개의 테스트 케이스를 입력받으세요. 3. 각 테이트 케이스가 회문이면 1을, 그렇지 않을 경우 0을 출력하세요. 핵심 포인트 수열의 크기는 최대 2,000이며 테스트 케이스의 최대 크기는 1,000,000입니..

문제 링크 : https://www.acmicpc.net/problem/11060 11060번: 점프 점프 재환이가 1×N 크기의 미로에 갇혀있다. 미로는 1×1 크기의 칸으로 이루어져 있고, 각 칸에는 정수가 하나 쓰여 있다. i번째 칸에 쓰여 있는 수를 Ai라고 했을 때, 재환이는 Ai이하만큼 오른쪽으로 www.acmicpc.net 문제 요약 1. 재환이는 일직선에 미로의 첫 번째 칸에 적혀있다. 그리고 N번째 칸으로 도착하는 것이 목표다. 2. 일직선 미로의 각 칸에는 숫자가 입력되어있다. 재환이는 N번째 칸에 있을 경우, N번째 칸에 있는 숫자만큼 최대 점프가 가능하다. 3. 예를들어 첫 번째 칸에 2가 적혀있을 경우, 재환이는 1칸을 점프하거나 2칸을 점프할 수 있다. 4. N번째 칸에 도달하기..

문제 링크 : https://www.acmicpc.net/problem/11048 11048번: 이동하기 준규는 N×M 크기의 미로에 갇혀있다. 미로는 1×1크기의 방으로 나누어져 있고, 각 방에는 사탕이 놓여져 있다. 미로의 가장 왼쪽 윗 방은 (1, 1)이고, 가장 오른쪽 아랫 방은 (N, M)이다. 준규는 www.acmicpc.net 문제 요약 1. 진수는 미로의 [1,1]에서 [N,M]으로 가려고 합니다. 2. 진수의 이동방향은 진수가 (r,c)에 있다고 가정할때, (r+1, c), (r, c+1), (r+1, c+1)로 이동할 수 있습니다. 3. 미로의 방 중에는 사탕이 놓여진 방이 있습니다. 진수가 최대한으로 가져갈 수 있는 사탕 갯수를 구하세요. 핵심 포인트 이 문제는 BFS로도 풀 수 있지..

The link : https://leetcode.com/problems/coin-change/ Coin Change - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com 문제 풀이는 다음과 같다. 1. 먼저 amount가 0일 경우, 정답은 어차피 0으로 고정되어있다. 이와 관련된 조건문을 맨 위에 적어주자. if(amount==0) return 0; 2. amount의 값 만큼 vector sum변수를 1개 생성한다. 이때 중요한 점이, int형 최대값으로 초기..

문제 링크 : https://www.acmicpc.net/problem/2096 2096번: 내려가기 첫째 줄에 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 숫자가 세 개씩 주어진다. 숫자는 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 중의 하나가 된다. www.acmicpc.net 이 문제는 메모리 제한이 걸려있으므로, 무턱대로 100,000*3의 배열을 만들었다가는 메모리 초과가 나온다. 때문에 배열의 사이즈를 크게 잡지 않고 값을 입력받을 방법이 필요하다. 문제 풀이는 다음과 같다. 1. 필요한 변수들을 설정하고, 첫 번째 줄의 값들을 저장한다. int n,a,b,c,x,y,z,maxi = 0, mini = 900001; cin >> n; cin >> a >> b >> ..

문제 링크 : www.acmicpc.net/problem/13398 13398번: 연속합 2 첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다. www.acmicpc.net 이 문제는 백준 11054번 가장 긴 바이토닉 부분 수열을 응용해서 풀 수있다. 각 숫자들을 지웠을 경우에 발생하는 최대값을 어떻게 도출하냐가 문제인데, 이를 위해 아래 3가지 배열을 생성한다. (1) 입력값 (2) i번째에서 끝나는 수열 (3) i번째에서 시작하는 수열 우리는 위의 (2)와 (3)을 통해, 최대값을 다음 두 케이스 중 하나로 도출해낼수 있다. i번째까지의 최대합 vs i-1번째까지 ..

문제 링크 : www.acmicpc.net/problem/11054 11054번: 가장 긴 바이토닉 부분 수열 첫째 줄에 수열 A의 크기 N이 주어지고, 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ N ≤ 1,000, 1 ≤ Ai ≤ 1,000) www.acmicpc.net 이 문제는 백준 11053번 가장 긴 증가하는 부분 수열의 확장판이다. 문제 풀이는 다음과 같다. 1. 증가하는 수열과 감소하는 수열을 나눠서 바라본다. 때문에 배열은 총 3개가 필요한데, 아래의 배열들이 필요하다. (1) 입력값 (2) 증가길이 (3) 감소길이 2. 정답변수의 초기값은 1로 선언해준다. 무슨일이 있어도 최소 증가길이는 1이 나올 수 밖에 없기 때문이다. 3. 증가하는 수열의 길이를 저장한다. 4. ..