문제k번 happiness 배열을 훑으면서 남아 있는 가장 큰 값을 더해서 반환한다. 단, 한 번 가장 큰 값을 뽑으면 그 다음엔 배열에 담긴 모든 값이 1씩 줄어들고 그 상태에서 가장 큰 값을 또 꺼내야 한다.나의 접근법happiness를 오름차순 정렬하고, k개만큼 앞에서 가장 큰 값에서 인덱스를 뺀 값을 더해간다. 단, 가장 큰 값에서 인덱스를 뺀 값은 최소 0이다.class Solution { public long maximumHappinessSum(int[] happiness, int k) { Arrays.sort(happiness); int n = happiness.length; for (int i = 0; i 코멘트시간복잡도는 코드 라인따라 계산해보..
백준 7562 나이트의 이동
www.acmicpc.net/problem/7562 7562번: 나이트의 이동 체스판 위에 한 나이트가 놓여져 있다. 나이트가 한 번에 이동할 수 있는 칸은 아래 그림에 나와있다. 나이트가 이동하려고 하는 칸이 주어진다. 나이트는 몇 번 움직이면 이 칸으로 이동할 수 www.acmicpc.net 이 문제를 처음 보면 어떻게 풀어야 할 지 감이 안 잡힌다. 그러나 잘 생각해보면 BFS를 이용해서 풀 수 있는 문제라는걸 알 수 있다. 나이트가 이동할 수 있는 방향은 왼쪽과 같다. 문제는 이렇게 이동할 수 있는 나이트를 시작위치에서 종료위치로 옮기는 최소횟수를 구하는 것이다. 차례대로 생각을 해보자면, 나이트는 시작위치에서도 저 8개 위치로만 이동할 수 있고, 8개 위치 중 하나를 골라 이동한 뒤에 또 8개 ..