BOJ 썸네일형 리스트형 [백준][JAVA] 1463 - 1로 만들기 문제 출처 : https://www.acmicpc.net/problem/1463 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net 문제 설명 N의 범위가 꽤나 크지만 시간 제한이 0.15초로 굉장히 짧은 걸로 봐서, dp문제임을 짐작할 수 있습니다. dp배열에 해당하는 d에는 각 인덱스에 해당하는 수를 1로 만들기 위해 필요한 최소 연산의 횟수가 각각 들어가 있고, 메모이제이션을 해 가며 답을 도출했습니다. 초기값을 d[3]까지 넣어준 다음, 4부터 N까지 반복문을 돌며 i가 2와 3으로 모두 나누어 떨어지는 경우, 2로만 또는 3으로만 나눠 떨어지는 경우 그리고 2와 3 모두 나누어 떨어지지 않는 경우로 나눴습니다. i는 .. 더보기 [백준][JAVA] 1149번 - RGB거리 문제 출처 : https://www.acmicpc.net/problem/1149 1149번: RGB거리 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 www.acmicpc.net 설명 전형적인 DP문제였습니다. 재귀처럼 FLAT하게 생각하는게 중요한 유형이죠. 여기에서 dp용 배열로 사용한 d는 1번 집부터 N번 집까지 집을 칠하는 비용의 최솟값이 들어있습니다. 예를 들어, d[N][0] 은 N번집에 빨간색을 칠했을 경우에 1번 집부터 N번 집까지 집을 칠하는 비용의 최솟값이 들어있는 것이죠. 그런 식으로 계속해서 min값만을 골라 거기.. 더보기 [백준][JAVA] 2304 - 창고 다각형 문제 출처 : https://www.acmicpc.net/problem/2304 2304번: 창고 다각형 첫 줄에는 기둥의 개수를 나타내는 정수 N이 주어진다. N은 1 이상 1,000 이하이다. 그 다음 N 개의 줄에는 각 줄에 각 기둥의 왼쪽 면의 위치를 나타내는 정수 L과 높이를 나타내는 정수 H가 한 개의 www.acmicpc.net 문제 설명 실버2 문제치고 어려운 문제였습니다ㅠㅠ 코드에 최대한 주석 달아놨으니 참고해 주시면 좋을 것 같습니다. 이 문제의 핵심은 높이가 가장 높은 꼭대기를 구하는 것인데, 왼쪽에서 오른쪽 방향으로 진행해 나가며 current Top point를 변경시키면서 찾습니다. 꼭대기와 면적까지 계산한 뒤에, 구한 꼭대기를 기반으로 오른쪽에서 왼쪽 방향으로 아직 구하지 못한.. 더보기 [백준][JAVA] 2578 - 빙고 문제 출처: https://www.acmicpc.net/problem/2578 2578번: 빙고 첫째 줄부터 다섯째 줄까지 빙고판에 쓰여진 수가 가장 위 가로줄부터 차례대로 한 줄에 다섯 개씩 빈 칸을 사이에 두고 주어진다. 여섯째 줄부터 열째 줄까지 사회자가 부르는 수가 차례대로 www.acmicpc.net 문제 설명 단순 구현 문제입니다. 사회자가 부른 숫자를 자신의 빙고판에 표시하다가, 최소 12개 이상부터 빙고가 가능하기 때문에 12개 이후에는 사회자가 부른 수를 빙고판에 표시할 때마다 빙고 상태인지를 체크하게 했습니다. 여기서 중요한 점은, 빙고 체크가 한번 끝날 때마다 다시 cnt 변수를 0으로 초기화 해주어야 한다는 점입니다! 코드 import java.util.Scanner; public .. 더보기 [BOJ][JAVA] 11866 - 요세푸스 문제 0 문제 출처 : https://www.acmicpc.net/problem/11866 11866번: 요세푸스 문제 0 첫째 줄에 N과 K가 빈 칸을 사이에 두고 순서대로 주어진다. (1 ≤ K ≤ N ≤ 1,000) www.acmicpc.net 문제 설명 자료구조 Queue(FIFO)를 사용하는 문제였습니다. 물론 문제를 읽고 바로 큐를 떠올리기는 쉽지 않습니다만, "원(Circle)형 문제"이기 때문에 K번째 사람 전까지의 사람들을 dequeue & enqueue하면 K번째 사람을 제거하고 나서도 원에서의 순서가 그대로 유지되기 때문에 큐를 사용하면 간단하게 문제가 해결됩니다. 코드 import java.util.LinkedList; import java.util.Queue; import java.util.. 더보기 [BOJ][JAVA] 10773 - 제로 문제 출처 : https://www.acmicpc.net/problem/10773 10773번: 제로 첫 번째 줄에 정수 K가 주어진다. (1 ≤ K ≤ 100,000) 이후 K개의 줄에 정수가 1개씩 주어진다. 정수는 0에서 1,000,000 사이의 값을 가지며, 정수가 "0" 일 경우에는 가장 최근에 쓴 수를 지우고, 아닐 경 www.acmicpc.net 문제 설명 풀이 방법으로 스택(FILO)을 쉽게 떠올릴 수 있는 문제입니다. 입력이 0일 때마다 스택을 pop하고, 그렇지 않으면 그 수를 스택에 넣습니다. 입력이 끝나면, 스택이 빌 때까지 pop하면서 pop한 수를 결과에 누적시켜 더하면 되는, 비교적 간단한 문제였습니다. 코드 import java.util.Scanner; import java... 더보기 [BOJ][JAVA] 7568 - 덩치 문제 출처 : https://www.acmicpc.net/problem/7568 7568번: 덩치 우리는 사람의 덩치를 키와 몸무게, 이 두 개의 값으로 표현하여 그 등수를 매겨보려고 한다. 어떤 사람의 몸무게가 x kg이고 키가 y cm라면 이 사람의 덩치는 (x, y)로 표시된다. 두 사람 A 와 B의 덩 www.acmicpc.net 문제 설명 그렇게 어렵지 않은 문제인데, 너무 어렵게 생각해서 초반에 좀 헤멨던 문제입니다. 저처럼 복잡하게 잘못 생각하지 않으려면, 다음과 같이 생각하시면 됩니다. 각 사람의 덩치 등수는 자신보다 "더 큰 덩치", 즉 키와 몸무게가 확실히 자기보다 더 큰 사람의 수로 정해집니다. 따라서, 덩치 등수 정하기 애매한 것은 생각하지 않고, 그냥 자기보다 확실히 더 큰 사람이.. 더보기 [BOJ][JAVA] 1181 - 단어 정렬 문제 출처 : https://www.acmicpc.net/problem/1181 1181번: 단어 정렬 첫째 줄에 단어의 개수 N이 주어진다. (1 ≤ N ≤ 20,000) 둘째 줄부터 N개의 줄에 걸쳐 알파벳 소문자로 이루어진 단어가 한 줄에 하나씩 주어진다. 주어지는 문자열의 길이는 50을 넘지 않는다. www.acmicpc.net 문제 설명 Comparator와 contains함수를 잘 활용해서 풀어야 하는 문제입니다. 인터넷의 다른 포스팅들도 대부분 풀이가 같은 걸로 보아, 이 풀이로 거의 정형화된 문제인 것 같습니다. compare(o1, o2)와 o1.compareTo(o2)는 공통적으로 o1에서 o2를 빼는데, 오버라이딩을 통해 연산의 대상을 변경할 수 있습니다. 그리고 이 두 함수는 연산의.. 더보기 이전 1 2 3 4 다음
