끼루루룩

1. 문제 https://programmers.co.kr/learn/courses/30/lessons/42898 코딩테스트 연습 - 등굣길 계속되는 폭우로 일부 지역이 물에 잠겼습니다. 물에 잠기지 않은 지역을 통해 학교를 가려고 합니다. 집에서 학교까지 가는 길은 m x n 크기의 격자모양으로 나타낼 수 있습니다. 아래 그림은 m = programmers.co.kr 2. 설명 일단 물 웅덩이가 있는 곳은 -1로 표시해줬다 ! 그리고 배열을 쭉 살피면서 길을 찾아갔다. 중학교? 고등학교? 때 배운 길찾기 문제를 코드로 옮기는 듯한 문제였다. 3. 코드 class Solution { public int solution(int m, int n, int[][] puddles) { int answer = 0; ..

1. 문제 https://www.acmicpc.net/problem/9461 9461번: 파도반 수열 문제 오른쪽 그림과 같이 삼각형이 나선 모양으로 놓여져 있다. 첫 삼각형은 정삼각형으로 변의 길이는 1이다. 그 다음에는 다음과 같은 과정으로 정삼각형을 계속 추가한다. 나선에서 가장 긴 � www.acmicpc.net 2. 설명 점화식이 dp[n] = dp[n-1] + dp[n-5] 였다. 또한 n의 범위가 100까지이기 때문에 int형으로 dp를 선언하면 틀렸다고 나온다. 이부분은 항상 헷갈린당; 3. 코드 import java.util.StringTokenizer; import java.io.BufferedReader; import java.io.IOException; import java.io.I..

1. 문제 https://www.acmicpc.net/problem/11727 11727번: 2×n 타일링 2 2×n 직사각형을 1×2, 2×1과 2×2 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×17 직사각형을 채운 한가지 예이다. www.acmicpc.net 2. 설명 하나씩 해보면서 규칙찾아서 풀었다. 짝수일 때는 그 전의 dp 2배에 +1을 해주어야 했고, 홀수일 때는 전의 dp 2배에 -1을 해주어야 했다. 규칙만 찾으면 쉽게 풀 수 있는 문제 3. 코드 import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner scan = new Scanner(Syste..

1. 문제 https://www.acmicpc.net/problem/10844 10844번: 쉬운 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 2. 설명 6번 틀리고 맞은 문제 ㅋㅋㅋㅋㅋㅋ 첫 접근으로 점화식을 dp[n] = dp[n-1] * 2 - 1 로 세웠었는데, 백준 채점기가 틀렸다고 답해주셨다. 다르게 규칙찾는 방법으로, 공간을 늘려서 자릿수를 n까지 늘려가면서 구하는 방식으로 풀었다. 정답을 1,000,000,000으로 나눈 나머지를 출력하라고 하는 부분에서도 막힌게 있었는데, 그 전에는 sum+=dp[n-1][i]를 하고 전체 값을 mod로 나눴었다. 하지만 위 코드와 값 하나하나를 mod로 나눈 값이랑 결과가 다르기 때문에 아..

1. 문제 https://www.acmicpc.net/problem/1912 1912번: 연속합 첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다. www.acmicpc.net 2. 설명 dp[i-1] + arr[i] 와 arr[i] 를 비교했을 때, arr[i]값이 더 크면 이 전에 더해왔던 연속합들을 버리고 다시 i부터 시작하면 된다. dp[n]이 아니라 중간에서 최댓값이 나올 수 있기 때문에 max를 두어 dp[i]의 최댓값을 삽입! 3. 코드 import java.util.StringTokenizer; import java.io.BufferedReader; imp..

1. 문제 https://www.acmicpc.net/problem/2156 2156번: 포도주 시식 효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 같은 두 가지 규 www.acmicpc.net 2. 설명 반례를 생각못해서 틀렸었다. 연속해서 3잔을 못마신다는 의미에서 저번에 푼 계단 오르기(백준-2579) 문제랑 비슷했다. 따라서 식 구하는 것도 비슷하게 구하면 된다. 하지만 저번 문제와 다른점으로 이 문제에선 포도주를 연속해서 2번이상 안마실 수 있다. 따라서 이 반례를 고려해서 dp[n]을 구할 때 dp[n-1]과 비교하여 큰 값을 넣어줬다. 3. 코드 import java..

1. 문제 https://www.acmicpc.net/problem/2193 2193번: 이친수 0과 1로만 이루어진 수를 이진수라 한다. 이러한 이진수 중 특별한 성질을 갖는 것들이 있는데, 이들을 이친수(pinary number)라 한다. 이친수는 다음의 성질을 만족한다. 이친수는 0으로 시작하지 않 www.acmicpc.net 2. 설명 손으로 계산해서 점화식을 얻으니까 피보나치랑 같았다. 그렇게 dp배열해서 정답 제출하니까 틀리더라? ?? int 배열이 피보나치 감당할 수 있는 범위가 42?정도 까지 였던거 같다. 따라서 long 타입으로 선언해야 된다. 3. 코드 import java.util.Scanner; public class Main { public static void main(Stri..

1. 문제 https://www.acmicpc.net/problem/2579 2579번: 계단 오르기 계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점 www.acmicpc.net 2. 설명 dp배열 초기화 때문에 헤맨 문제 무조건 첫번 째 계단부터 시작해야 되는 줄 알았는데 그런 조건은 없다. 마지막 계단만 밟으면 됨. 따라서 dp[2]에 첫번 째 계단, 두번 째 계단을 밟을 경우와 첫번 째 계단, 세번 째 계단을 밟을 경우 중 최댓값을 삽입해야 한다. 3. 코드 import java.util.StringTokenizer; import java.io.BufferedReade..