Java/Algorithms

문제 접근 방식 배열에서 특정 부분만 확인 했을 때 팰린드롬인지 판별하는 문제다. DP 문제이긴 하지만 이전 값을 사용해 테이블을 채워나가는 방식은 아니고 길이별로 팰린드롬인지 직접 확인해서 테이블에 저장해 s와 e를 입력 받을 때마다 매번 계산하지 않고 저장된 값을 읽는 방식이다. 1, 2, 1, 3, 1, 2, 1 위와 같은 배열의 경우에는 다음과 같은 테이블이 만들어진다. 1 2 1 3 1 2 1 1 T F T F F F T 2 T F F F T F 1 T F T F F 3 T F F F 1 T F T 2 T F 1 T 숫자가 하나인 경우는 무조건 팰린드롬이니 참으로 설정해두고 2개 이상인 경우만 판단하면 되고, 시작점이 끝점보다 큰 경우는 없기 때문에 자기 자신의 인덱스 이전은 신경 쓸 필요가 없..

문제 접근 방식 1인 부분으로만 이루어진 정사각형 중 가장 큰 정사각형을 찾아야 한다. 1 11 11 111 111 111 위와 같이 1로만 이루어진 곳을 찾아야 하는데 1인 곳을 발견할 때마다 주변을 한 칸씩 넓혀가며 모두 1인지 확인하는 것은 시간초과가 날 것이 확실하기 때문에 그렇게 무식하게 풀 수는 없다. 00 01 위의 경우를 생각해보면 1 주변은 모두 0이기 때문에 정사각형이 될 수 없고 크기가 1인 정사각형 하나만 가능하다. 11 11 1 > 2 ... > n 순으로 길이를 늘려주기만 하면 된다. 풀이 public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new Buf..

문제 접근 방식 이전 동전 문제처럼 k원을 만드는 모든 경우의 수를 구하는 것이 아니라 가장 적은 수의 동전을 사용해 k원을 만들 수 있는 경우를 구해야 한다. 5원, 1원, 12원 총 3개의 동전으로 15원을 만들어야 할 때 5원으로 15원을 만들 수 있는 경우를 먼저 생각해 보자 1원을 만드는 경우 : X 2원을 만드는 경우 : X 3원을 만드는 경우 : X 4원을 만드는 경우 : X 5원을 만드는 경우 : 1 6원을 만드는 경우 : X 7원을 만드는 경우 : X 8원을 만드는 경우 : X 9원을 만드는 경우 : X 10원을 만드는 경우 : 2 11원을 만드는 경우 : X 12원을 만드는 경우 : X 13원을 만드는 경우 : X 14원을 만드는 경우 : X 15원을 만드는 경우 : 3 위와 같이 5원..

문제 접근 방식 [백준] 2293번 : 동전 1 문제 접근 방식 1원, 2원, 5원 총 3가지의 동전으로 1원부터 10원을 만드는 경우를 적어보면 다음과 같다. 11 211 2 3111 12 41111 112 22 511111 1112 122 5 6111111 11112 1122 15 222 71111111 111112 11122 115 1222 25 811111111 1 da9dac.tistory.com 위의 문제와 입출력만 좀 다를 뿐 사실상 풀이가 같은 문제라 설명은 생략하겠다. 풀이 class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new Input..

문제 접근 방식 DP로 풀 필요도 없이 규칙만 찾으면 연산 한 줄로도 풀 수 있는 문제지만 그냥 DP로 풀어봤다. 우선 DP 테이블은 불리언 타입의 1차원 배열로 생성한 후에 상근이가 이기는 경우를 true, 창영이가 이기는 경우를 false로 채워주면 된다. 자기 순서에 1, 3, 4개 중 한 번씩 가져갈 수 있으니 이 경우에 상근이는 무조건 이길 수 있고 1, 3, 4번의 초기값은 true로 설정해준다. 9까지 직접 계산해 가며 표를 만들어보면 알 수 있는데 n번째 수를 가져가는 경우 중 상근이가 한 번이라도 가져가는 경우가 있다면 무조건 상근이가 이기는 경우이기 때문에 상근이가 처음에 1개를 가져가거나 3개를 가져가거나 4개를 가져간 후에 창근이가 지는 경우가 한 번이라도 있다면 상근이가 이기는 것..

문제 접근 방식 풀고 나서도 이게 그래프인지 DP 풀이인지 모르겠는 문제였다. 우선 그래프의 한 정점을 기준으로 위와 같이 이동할 수 있으며 2차원 배열을 처음부터 끝까지 돌면서 위와 같이 이동만 해주며 DP 테이블을 채워주면 된다. 따로 방문여부를 기록하지 않고 DP 테이블의 값이 0인지 아닌지로 확인하려 했는데 정점의 값이 음수인 경우도 있어서 합이 0일 때가 있을 수 있기 때문에 따로 방문 여부를 기록할 불리언 배열을 사용했다. 각 정점(i, j)에서 갈 수 있는 정점들을 방문하며 처음 방문한 정점(x, y)이면 방문 여부를 참으로 바꾸고, (x, y)의 DP 테이블에 (i, j) 테이블의 값 + 현재 정점의 값을 기록하고 이미 방문한 정점이라면 이미 기록된 값과 새로운 값 중 더 작은 값을 기록한..

문제 접근 방식 1원, 2원, 5원 총 3가지의 동전으로 1원부터 10원을 만드는 경우를 적어보면 다음과 같다. 11 211 2 3111 12 41111 112 22 511111 1112 122 5 6111111 11112 1122 15 222 71111111 111112 11122 115 1222 25 811111111 1111112 111122 1115 11222 125 2222 9111111111 11111112 1111122 11115 111222 1125 12222 225 101111111111 111111112 11111122 111115 1111222 11125 112222 1225 22222 55 다시 1원만 사용한 경우, 1원과 2원을 사용한 경우, 세 가지 동전을 모두 사용한 경우로 경..

문제 접근 방식 카드를 n개 살 때, 가장 돈을 많이 쓰는 경우를 구해야 한다. i번째 카드팩에는 카드가 i개 들어있다 했으니 만약 카드를 4개 사야한다 가정하면 1번팩 + 1번팩 + 1번팩 + 1번팩 1번팩 + 1번팩 + 2번팩 1번팩 + 3번팩 2번팩 + 2번팩 4번팩 위와 같은 경우의 수가 만들어진다. 4개가 아닌 3개로 줄여보면 다음과 같을 것이고 1번팩 + 1번팩 + 1번팩 1번팩 + 2번팩 3번팩 2개로 줄이면 다음과 같다. 1번팩 + 1번팩 2번팩 1개면 당연히 1번팩 하나만 살 수 있다. 결국 n개를 고를 때 i번 팩을 골랐다면 n-i개를 고를 수 있고 (i번 팩값 + n-i개를 고를 수 있는 경우 가장 큰 값) 이 된다. 이를 dp[i]를 채울 때마다 1번 팩을 고른 경우부터 i번 팩을 ..