Algorithm (57) 썸네일형 리스트형 [백준] 14501번: 퇴사 문제링크 : https://www.acmicpc.net/problem/14501 문제풀이 동적계획법으로 풀 수 있는 문제이다. 1일까지 상담했을 때 최대 금액, 2일까지 상담했을 때 최대 금액을 차례로 더하여 저장해놓는다. 1) 1일까지 상담했을 때 최대 금액은 10이다. 2) (2일을 포함하여) 2일까지 상담했을 때 최대 금액은 20이다. 왜냐하면 1일에 상담을 받으면 3일이 걸려 2일에는 상담을 받을 수 없기 때문이다. 3) (3일을 포함하여) 3일까지 상담했을 때 최대 금액은 10이다. 왜냐하면 1일에 상담을 받으면 3일이 걸려 3일에는 상담을 받을 수 없고, 마찬가지로 2일에도 상담을 받으면 5일이 걸려 3일에 상담을 받을 수 없다. 4) (4일을 포함하여) 4일까지 상담했을 때 최대 금액은 30.. [백준] 4447번: 좋은놈 나쁜놈 문제링크 : https://www.acmicpc.net/problem/4447 문제풀이 입력받은 히어로의 이름에 'G', 'g', 'B', 'b'의 개수를 센다. String으로 받아 charAt()으로 문자 하나씩 확인하여 개수를 확인한다. 'g'와 'b'의 개수가 같으면 "GOOD", 'b'가 더 많으면 "A BADDY", 적으면 "NEUTRAL"을 붙여서 출력한다. 소스코드 package baekjoon; import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; public class P4447 { public static void main(String[] args) throws IOExce.. [백준] 7785번: 회사에 있는 사람 문제링크 : https://www.acmicpc.net/problem/7785 문제풀이 문제만 처음 보고서는 쉬운 문제인 줄 알았는데, 시간초과가 문제였다. (N 0) { String str = br.readLine(); StringTokenizer st = new StringTokenizer(str); String name = st.nextToken(); String inout = st.nextToken(); if (inout.equals("enter")) { log.put(name, true); } else { log.put(name, false); } } Iterator iterator = log.keySet().iterator(); while (iterator.hasNext()) { String .. [백준] 2217번: 로프 문제링크 : https://www.acmicpc.net/problem/2217 문제풀이 각 로프의 최대 중량이 아래와 같다고 하면, 1) 5짜리 로프를 선택, 최대 5만큼의 중량이 걸린다고 하면, 세 로프로 들 수 있는 최대 중량은 5 X 3 = 15가 된다. 2) 8짜리 로프를 선택, 최대 8만큼의 중량이 걸린다고 하면, 5짜리 로프로는 들 수 없다. (최대가 5이므로) 따라서 8, 13짜리 로프에 각각 8씩 걸리게 되어 최대 중량은 8 X 2 = 16이 된다. 3) 13짜리 로프를 선택, 최대 13만큼의 중량이 걸린다고 하면, 5와 8짜리 로프는 사용할 수 없다. 따라서 13짜리 로프로 들 수 있는 최대 중량은 13 X 1 = 13이 된다. 따라서 이 경우 최대 중량은 2번으로 도출된 16이 된다. .. [백준] 11812번: K진 트리 문제링크 : https://www.acmicpc.net/problem/11812 문제풀이 처음엔 DFS로 풀으려고 했는데, 부모노드까지 갔다가 되돌아 오는 작업이 생각보다 복잡했다. LCA 알고리즘 분류에 속한다고 적혀있어서 알고리즘을 찾아보았다. LCA 알고리즘이란 공통 조상을 찾는 알고리즘을 말한다. 즉 입력받은 각 두 노드가 공통된 조상을 가질 때 까지 이동한 거리를 합하면, 두 노드 사이의 거리가 된다. 그러면 먼저 각 노드의 부모 노드를 구해야 하는데, 부모 노드의 번호는 다음 공식으로 구할 수 있다. 이 공식을 이용하여, 두 노드의 부모가 같아질 때 까지 거리를 증가시키면 된다. 위와 그림과 같은 경우 거리는 4가 된다. 7 → 2 → 1 (거리 : 2) 8 → 3 → 1 (거리 : 2) --.. [백준] 1057번: 토너먼트 문제링크 : https://www.acmicpc.net/problem/1057 문제풀이 문제에서 라운드마다 번호가 1부터 다시 매겨진다고 했던 것이 힌트인 것 같다. 테스트 케이스를 예로 들면, 8번 9번은 라운드가 끝날 때 마다 아래와 같이 번호가 바뀐다. 8 → 4 → 2 → 1 9 → 5 → 3 → 2 결국 김지민과 임한수의 번호가 같게 되면, 그 라운드에서 대결을 하게 된다. 서로 대결을 하지 않는 경우 -1을 출력하라고 해서 while문에 조건을 어떻게 추가해야 하나 고민했는데.. 김지민과 임한수는 서로 대결하기 전까지 항상 이긴다는 조건이 있으므로, 대결을 하지 않는 경우는 없는 것 같다. 소스코드 package baekjoon; import java.io.BufferedReader; impo.. [백준] 1149번: RGB거리 문제링크 : https://www.acmicpc.net/problem/1149 문제풀이 처음엔 주어진 테스트 케이스를 보고도 이해가 잘 안갔는데, 동적 계획법으로 풀 수 있는 문제였다. 문제와 같은 경우, 아래와 같이 칠을 하면 최솟값 96이 나온다. 집 a부터 차례로 색을 칠한다고 하면, 칠할 수 있는 경우는 아래와 같다. b집을 빨강으로 칠한다고 하면, 옆집인 a는 초록 또는 파랑으로 칠할 수 밖에 없다. 따라서 b를 빨강으로 칠했을 때 최소비용은 a를 초록으로 칠했을 때 드는 비용, a를 파랑으로 칠했을 때 드는 비용 중 최소 비용을 더한 값과 같다. 마지막 집 c를 빨강으로 칠했을 때 최소비용은 색칠한 칸들의 네가지 경우 중 가장 최소비용을 더한 값과 같다. 따라서, i번째 집에 오기까지 최소비용.. [백준] 2562번: 최댓값 문제링크 : https://www.acmicpc.net/problem/2562 문제풀이 데이터를 입력받을 때마다 그 값이 최댓값인지 비교해서 저장해놓은 후 출력한다. 소스코드 package baekjoon; import java.io.*; public class P2562 { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int max = 0; int index = 0; for (int i = 0; i < 9; i++) { int num = Integer.parseInt(br.readLine()); if (num .. 이전 1 2 3 4 ··· 8 다음 목록 더보기
