6-6화이탱

https://www.acmicpc.net/problem/3109 3109번: 빵집 유명한 제빵사 김원웅은 빵집을 운영하고 있다. 원웅이의 빵집은 글로벌 재정 위기를 피해가지 못했고, 결국 심각한 재정 위기에 빠졌다. 원웅이는 지출을 줄이고자 여기저기 지출을 살펴보던 www.acmicpc.net 난이도: 골 2 그리디 알고리즘 문제이다. 오른쪽 위, 오른쪽, 오른쪽 아래의 방향으로 움직여야 한다는게 포인트이다! 원웅빵집 다른 곳 | ↗ → ↘ | 또한 flag값을 생성하여 길이 완성되면 더 이상 길을 가지 않도록 하고 길 완성에 실패하면 이 길은 못가는 길임을 표시하도록 visited true 한다 import java.io.BufferedReader; import java.io.IOException; ..

https://www.acmicpc.net/problem/1339 1339번: 단어 수학 첫째 줄에 단어의 개수 N(1 ≤ N ≤ 10)이 주어진다. 둘째 줄부터 N개의 줄에 단어가 한 줄에 하나씩 주어진다. 단어는 알파벳 대문자로만 이루어져있다. 모든 단어에 포함되어 있는 알파벳은 최대 www.acmicpc.net 난이도 : 골드4 그리디 알고리즘 문제로, 1. 알파벳별의 배열을 생성하여 A~Z를 0~25의 인덱스로 가정한다! 알파벳의 자릿수에 따른 값을 배열에 넣는다! ex) ABC 첫번째 A는 알파벳 배열의 0번째에 해당한다. 100자리의 수이기에 알파벳배열에 +100 두번째 B는 알파벳 배열의 1번째, 10의 자릿수이기에 +10 세번째 C는 알파벳 배열의 2번째, 1의 자리이기에 +1 이렇게 알파..

https://www.acmicpc.net/problem/19701 19701번: 소 운전한다. 1번 도시에서 2번 도시로 가고 싶다면, 첫 번째 고속도로를 타고 곧바로 갈 수 있다. 이 고속도로의 길이는 2이고, 이 고속도로에 있는 휴게소의 돈까스의 맛은 1이므로, 이 경로로 이동한다면, 문 www.acmicpc.net 난이도 : 골드 1 다익스트라 문제로, 돈까스를 먹었을 경우와 안먹었을 경우로 나누어서 확인하면 된다. dist[idx][0] -> 안먹었을 경우 dist[idx][1] -> 먹었을 경우 최종적으로 두 값중 작은 값을 출력한다. 그리고 59퍼에서 시간초과가 나지 않도록 !! dist[현재idx][현재먹음여부] 가 현재 가중치값보다 작다면 더이상 확인할 필요가 없기 때문에 continue..

https://www.acmicpc.net/problem/1863 1863번: 스카이라인 쉬운거 첫째 줄에 n이 주어진다. (1 ≤ n ≤ 50,000) 다음 n개의 줄에는 왼쪽부터 스카이라인을 보아 갈 때 스카이라인의 고도가 바뀌는 지점의 좌표 x와 y가 주어진다. (1 ≤ x ≤ 1,000,000. 0 ≤ y ≤ 500,000) 첫 www.acmicpc.net 골드 4문제로, 스택을 사용하여 문제를 풀 수 있다! 예를 들어 1 1 2 2 3 3 4 1 일 경우, 앞에 있는 높이들이 현재 높이보다 크다면 건물이 있는 것이기에 스택에 1 ,2 ,3 을 넣고 1이 들어올 차례에 while문을 돌려서 앞에 있는 높이들 중에 1보다 큰 높이가 있는지 확인한다. 크다면, stack.pop을 하여 count+1을..

https://www.acmicpc.net/problem/5052 5052번: 전화번호 목록 첫째 줄에 테스트 케이스의 개수 t가 주어진다. (1 ≤ t ≤ 50) 각 테스트 케이스의 첫째 줄에는 전화번호의 수 n이 주어진다. (1 ≤ n ≤ 10000) 다음 n개의 줄에는 목록에 포함되어 있는 전화번호가 www.acmicpc.net 정렬을 사용하여 문제를 해결할 수 있었다! 처음에 제출했을때 왜맞틀이라 당황했지만 1 2 1 21 와 같은 반례가 존재한다. 두번째 숫자가 12일 경우에는 NO이지만 21이기때문에 YES이다. 따라서 .startWith()를 사용하여 구분하였다. import java.io.BufferedReader; import java.io.IOException; import java.i..

https://www.acmicpc.net/problem/2228 2228번: 구간 나누기 N(1 ≤ N ≤ 100)개의 수로 이루어진 1차원 배열이 있다. 이 배열에서 M(1 ≤ M ≤ ⌈(N/2)⌉)개의 구간을 선택해서, 구간에 속한 수들의 총 합이 최대가 되도록 하려 한다. 단, 다음의 조건들이 만족되 www.acmicpc.net DP와 누적합 문제로 풀어보면 좋을 문제인 듯 하다!! 점화식을 생각해내기 어려운 부분이 있어서 꼭 풀어보시면 좋겠다! 필자도 조만간 한번 더 풀어볼 예정이다 ,, ㅎㅎ 풀이 1.누적합을 이용하여 sum 배열에 넣어주고 2.dp 배열을 생성하여 숫자의 최솟값은 -32768이고 N은 100개까지 이루어지므로, dp[0][1~m]까지를 -3276800으로 초기화한다. 3. d..

https://www.acmicpc.net/problem/1947 1947번: 선물 전달 경우의 수를 1,000,000,000으로 나눈 나머지를 첫째 줄에 출력한다. www.acmicpc.net 1명 - 0 2명 - 1 3명 - 2 4명 - 9 5명 - 44 이기에 (dp[i-1]+dp[i-2])*(i-1) 의 점화식이 성립된다! 해당 점화식과 1000000000으로 나눈 값을 출력하면 간단히 해결~! import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; public class Main { public static void main(String[] args) throws NumberFormat..

https://www.acmicpc.net/problem/2157 2157번: 여행 첫째 줄에 N(1 ≤ N ≤ 300), M(2 ≤ M ≤ N), K(1 ≤ K ≤ 100,000)가 주어진다. K는 개설된 항공로의 개수이다. 다음 K개의 줄에는 각 항공로에 대한 정보를 나타내는 세 정수 a, b, c(1 ≤ a, b ≤ N, 1 ≤ c ≤ 1 www.acmicpc.net DP 문제로 처음에 생각해내기 어려웠다.. 풀이 1. 리스트 배열을 만들어서 배열의 인덱스는 출발지, 리스트에는 도착지와 점수를 넣는다. ( 만일, 도착지가 출발지보다 작은 수라면 동쪽이동이기 때문에 스킵!) 2. dp 이차원배열을 생성하여 "new int[몇번째로 방문한 것인지=> m+1][도착지 번호=>n+1] = 점수" 를 저장할..

https://www.acmicpc.net/problem/1398 1398번: 동전 문제 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 둘째 줄부터 T개의 줄에 초콜릿의 가격이 주어진다. 가격의 1015보다 작거나 같은 자연수이다. www.acmicpc.net 1 10 25 100 1000 2500 10000 1000000 250000 이렇게 100을 곱한 값으로 나눌 수 있다. 사이즈가 100인 dp 배열을 만들어, 해당 인덱스의 값일 경우 지불해야 하는 동전의 개수를 세팅해놓는다. dp[input 값에 %100한 값] 을 모두 더하면 필요한 동전의 개수가 나온다. import java.io.BufferedReader; import java.io.IOException; import java.io.In..

https://www.acmicpc.net/problem/17609 17609번: 회문 각 문자열이 회문인지, 유사 회문인지, 둘 모두 해당되지 않는지를 판단하여 회문이면 0, 유사 회문이면 1, 둘 모두 아니면 2를 순서대로 한 줄에 하나씩 출력한다. www.acmicpc.net check메소드에서 while문으로 left와 right 를 하나씩 비교하면서 회문임을 확인한다. check2 메소드에서는 while문으로 left와 right 를 하나씩 비교하고, 같지 않다면 check(left+1,right) 와 check(left,right-1) 로 왼쪽 하나와 오른쪽 하나를 지웠을때 회문인지 확인한다! import java.io.BufferedReader; import java.io.IOExceptio..