문제https://www.acmicpc.net/problem/14501 14501번: 퇴사첫째 줄에 백준이가 얻을 수 있는 최대 이익을 출력한다.www.acmicpc.net 접근법DP를 사용해 풀었다. 점화식점화식을 만드는게 어려웠다. 처음엔 dp[i] = i일까지의 누적 최대 이익 이라고 세우고 풀어봤지만 잘 풀리지 않아서 아래와 같이 고쳐서 풀었다.dp[i] = i일부터 퇴사일까지의 최대 이익즉, 구하고자 하는 것은 dp[1]인 것이다. 따라서 dp 값을 마지막부터 1까지 구해야된다. 1일에 시작한 상담은 4일에 끝나기 때문에 1일부터 퇴사일까지 얻을 수 있는 최대 이익은 P[1] + dp[4]이다. 이 내용을 토대로 점화식을 좀 더 자세히 세워보자.dp[i] = P[i] + dp[i + T[i]]..
문제https://www.acmicpc.net/problem/14889 14889번: 스타트와 링크예제 2의 경우에 (1, 3, 6), (2, 4, 5)로 팀을 나누면 되고, 예제 3의 경우에는 (1, 2, 4, 5), (3, 6, 7, 8)로 팀을 나누면 된다.www.acmicpc.net 접근법주어진 능력치에 규칙이 있는 것이 아니기 때문에 완전 탐색을 해야겠다고 생각했다. 재귀 호출과 visited[] 배열을 사용한 완전 탐색을 사용했다. 코드import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.StringTokenizer;public class Main { ..
문제https://school.programmers.co.kr/learn/courses/30/lessons/42578 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr 접근법문제에 힌트가 들어있다. 바로 "조합"이다. 입출력 예제 1번을 보면 headgear 2개, eyewear 1개가 있다. 이때 headgear에서 나올 수 있는 경우의 수는 2C0 과 2C1 이고, eyewear에서 나올 수 있는 경우의 수는 1C1 과 1C0이다. 즉, 각 종류에서 의상은 1개 혹은 0개만 뽑으면 된다는 것이다. 여기서 주의할 점은 최소 한 개의..
문제https://www.acmicpc.net/problem/13458 13458번: 시험 감독첫째 줄에 시험장의 개수 N(1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 각 시험장에 있는 응시자의 수 Ai (1 ≤ Ai ≤ 1,000,000)가 주어진다. 셋째 줄에는 B와 C가 주어진다. (1 ≤ B, C ≤ 1,000,000)www.acmicpc.net 접근법쉬운 문제이지만 문제 풀 때 놓치기 쉬운 부분들이 있다. 나 역시 브론즈 주제에 5번이나 제출한게 너무 억울해서 정리해본다..... 알고리즘은 정말 쉬우니 혼자 생각해보길! 알고리즘이 맞는거 같음에도 불구하고 초반에 바로 "틀렸습니다"가 뜨는 경우는 long을 사용하지 않아서 틀린 경우가 주로 있다. 이 문제 역시 감독관의 최소 수가 ..
문제https://school.programmers.co.kr/learn/courses/30/lessons/87390 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr 접근법문제를 처음에 봤을 때는 문제에서 요구하는 그대로 2차원 배열을 만들어서 하면 되겠다고 생각했지만, n의 범위가 최대 107 이므로 2차원 배열을 생성하기엔 힘드니 규칙을 찾아야겠다고 생각했다. 규칙을 찾기 위해 문제를 그려보며 생각했다. 예제입출력 예의 두번째를 한번 그려보자. n = 4, left = 7, right = 14이 2차원 배열을 각 행씩 잘라서 붙이면 아래와 같고, 색칠..
문제https://www.acmicpc.net/problem/16236 16236번: 아기 상어N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 물고기가 최대 1마리 존재한다. 아기 상어와 물고기는 모두 크기를 가www.acmicpc.net 접근법최단 거리를 구하는 문제이기 때문에 BFS를 사용한다. 알고리즘먹을 수 있는 물고기가 남아있을 때까지 BFS를 반복해서 수행한다. 보통은 boolean[][] visited 배열을 사용해 방문 여부를 표시하지만, 나는 물고기를 먹으러 가는데 얼마나 걸리는지를 계산하기 위해 int[][] count를 사용해 해당 지점까지 얼마나 걸리는지를 나타내었다. BFS를 탐색을 하면서 아기 상어가..
문제https://www.acmicpc.net/problem/2749 2749번: 피보나치 수 3첫째 줄에 n이 주어진다. n은 1,000,000,000,000,000,000보다 작거나 같은 자연수이다.www.acmicpc.net 접근법문제 제목만 보고 피보나치 수는 금방 풀 수 있겠지~ 했는데 역시 골드 2인 이유가 있었다. 피사노 주기를 알아야 풀 수 있는 문제였다. 피사노 주기 (Pisano period): 피보나치 수를 어떤 수 K로 나눌 때, 나머지는 항상 주기를 가지게 된다. 주기의 길이를 P라고 할 때 N번째 피보나치 수를 M으로 나눈 나머지는 N%P번째 피보나치 수를 M으로 나눈 나머지와 같다.주기는 M = 10k일 때, 항상 15∗10(k−1)이다. 문제에서 1,000,000..
