Algorithm/Algorithm Problem

백준 2133 타일 채우기(DP)

2133번: 타일 채우기 3×N 크기의 벽을 2×1, 1×2 크기의 타일로 채우는 경우의 수를 구해보자. www.acmicpc.net 3 x 2 일땐 이렇게 총 3가지가 나온다 1x2. 2x1로만 타일을 만들어야하기 때문에 홀수개의 타일의 경우는 채울 수 없으므로 N이 홀수일 땐 불가하고 이런식으로 이어갈텐데 N = 4부터 가운데에 영향을 주는 애들이 하나씩 생기기 시작한다. 이런 경우를 모두 찾아서 더해주면 된다 for (int i = 4; i =0 ; j-=2) { dp[i] += dp[j] * 2; } }

백준 14238 출근 기록(DFS+DP) ★

14238번: 출근 기록 스타트링크에는 세명의 직원이 일을 하고 있다. 세 직원의 이름은 강호(A), 준규(B), 수빈(C) 이다. 이 회사의 직원은 특별한 룰을 가지고 있는데, 바로 하루에 한 명만 출근한다는 것이다. 3일간의 www.acmicpc.net A : 매일 출근 가능 B : 출근한 다음날 쉬어야함 C : 출근한 다음날, 다다음날 쉬어야함 처음 입력은 이상하게 BBA이렇게 나와도 되는데 이걸 다시 재조합해서 ABA처럼 올바른 출근 순서로 바꾸라는 것 1. 그리디 그러면 결국 B사이에 A나 C가 있어야하고 C사이에는 A,B가 있어야하니까 개수를 파악해야 되겠네 A는 많이 있어도 상관없음 B = b+1){ res[a + b + c] = 'B'; if (back1 != 'B'){ if (dfs(a,..

백준 1062 가르침(조합)

1062번: 가르침 첫째 줄에 단어의 개수 N과 K가 주어진다. N은 50보다 작거나 같은 자연수이고, K는 26보다 작거나 같은 자연수 또는 0이다. 둘째 줄부터 N개의 줄에 남극 언어의 단어가 주어진다. 단어는 영어 소문 www.acmicpc.net 뭔가 카카오 코딩테스트에서 많이 나올법만 문제 유형이였다. K개의 단어를 학습하려고 하고 anti - tica는 무조껀 단어에 존재한다고 하니까 5글자는 무조껀 학습이 되어야하는 상황이다. 그렇다면 K=5인 경우로 크게 나눠볼 수 있고 배워야하는 단어의 수 : X 라고 한다면 X = K-5라면, X개 중 K-5개를 뽑아서 check()해봐야하기 때문에 조합이 ..

SWEA 1983 조교의 성적 매기기(Map)

SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com Map을 이용한 indexing 문제였다. 처음에 문제를 이해하는데 N / 10 이라는 조건이 헷갈렸지만 30명이 있을 때 3명은 똑같은 점수를 받을 수 있으니 마지막으로 구한 idx에 3으로 나눠야 grade배열에 index로 접근할 수 있다는 의미였다. 나는 여기서 Map을 이용했는데 key가 아닌 value로 정렬하는 법이 핵심이였다. key로 정렬하는법은 TreeMap을 이용하면 간편하지만 value로 하기 위해선 list를 만들고 entitySet(), keySet()으로 초기화 시켜준다음 정렬하는게 포인트였다. List key_list = new Arr..

SWEA 1859 백만 장자 프로젝트(그리디) ★★

SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 물건의 매매가를 하루하루 순차적으로 봐야하기 때문에 정렬을 하지않고 O(N)으로 판단해야 하는 문제임을 파악했다. 처음에는 O(N^2)으로 기준을 하나 잡고 기준뒤에 있는 가장 큰 수를 찾은다음 매매를 하는 방식으로 최댓값을 구했지만 당연히 시간초과가 났다(N의 범위 : 1,000,000) 다음 방법으로 DP를 생각해봤다. dp[i]가 i번째 날에 얻을 수 있는 최댓값으로 정의를 했는데 i번째 날 가지고 있는 물건을 다 팔아야 dp가 최댓값이 될텐데 안팔고 나중에 더 큰수가 나타날 때 파는 경우가 생기기 때문에 dp값이 계속 바뀌므로 DP도 아니였다. 따라서, 정..

백준 3687 성냥개비(DP, 그리디)

3687번: 성냥개비 각 테스트 케이스에 대해서 입력으로 주어진 성냥개비를 모두 사용해서 만들 수 있는 가장 작은 수와 가장 큰 수를 출력한다. 두 숫자는 모두 양수이어야 하고, 숫자는 0으로 시작할 수 없다. www.acmicpc.net 가장 큰 수 - 111111xxxxx - 성냥 개수가 홀수면 3개(7) 쓰고 나머지 2개(1)로 이어붙이기 가장 작은 수 - xxxx888888 - 성냥을 많이 쓰면서 자리수를 최대한 줄여야 된다 DP Table에 min값을 저장한다 2 ~ 9까지 만들 수 있는 애들을 Queue에 넣고 성냥을 1~10까지 넣어 볼 수 있는 경우 다 넣는다 package pratice; import java.util.*; class Data{ int cnt; long num; publi..