말하는 컴공감자의 텃밭

문제를 잘 읽자 확실히 사업가는 다르다, 최솟값을 찾아야한다. 100명의 홍보를 원한다 하더라도 100명 이상의 비용이 더 저렴하다면 그 값을 출력해야했다. 간단하게 입력 받은 금액 당 홍보 인원을 통해 현재 인원 - 입력받은 인원으로 따져서 금액을 최신화 해주었다. 현재 인원에 대한 금액 최신화 -> 현재인원 - 입력 받은 인원 + 입력받은 금액 이랑 비교 + 추가로 금액의 최대가 100 이므로 +101 까지만 조회해서 효율을 챙겼다. HTML 삽입 미리보기할 수 없는 소스

하필 또 술먹고 풀어서 머리가 많이 안굴러가 고생한 문제다. 가장 많은 빌딩을 볼 수 있을때 몇개나 볼 수 있는지 구하는 문제이다. 처음에는 어떤 기준으로 보이려나 감이 안잡혀서 그림으로 표현해서 해결했다. 답은 기울기 였다. 현재 내가 있는 빌딩에서 바라보려는 빌딩의 사이가 막혀있다면 볼 수 없으니 기울기를 통해 이를 판단했다. 기울기 판단은 (현재 높이 - 판단할 빌딩 높이) / (현재 위치 idx - 판단할 빌딩 idx) 로 해주었다. 위 계산 방식으로 판단하면 왼쪽의 경우 기울기가 기준보다 크다면 볼 수 없고, 오른쪽의 경우 기울기가 기존보다 작다면 안보일것이다. 먼저 노랑색 포인트를 기준으로 예시를 들겠다. 현재 7높이의 위치하고 있고, idx는 12번이다. 양쪽은 언제나 확인할 수 있으며 그 ..

처음엔 이게 뭐지 감을 못잡았다. 무슨말이래 파일은 바로 옆에있는것만 합칠 수 있고, 순서에 따라 합이 달라지는데 우리는 최소값을 구해주면 된다. 누적합 문제죠~?~ 범위를 2차원 배열로 정해서 DP로 범위를 나눠주기로 했다. 위 예제만 봐도 알겠지만 연산이 가장 적은게 훌륭하다. 최종 값은 결국 두 덩이를 합치는것이다. 하나를 A 하나를 B로 정한다면 합쳐진 A와 합쳐진 B가 더해져서 값을 구하는것 이므로 범위를 정하고, Mid를 조정해서 최소값을 찾아주면 되겠다. 범위를 늘려나가면서 저장해 준다. range 변수를 1부터 증가시켜 N 까지 더한 값으로 올라가고, start와 end 변수로 인덱스를 할당한다. 범위의 최소값을 구하고, 누적합을 통해 중간 연산을 더해준다. -> 누적합은 end에서 sta..

문제가 너무 간단해 보였는데.. 진짜 한참 한참 걸린 문제다. 열받으면서 풀었는데 까먹을까봐 까먹을랑 말랑할때 정리한다. 먼저 지름길 갯수와, 거리가 주어진다. 지름길은 시작점과 끝점, 소모되는 시간이 주어지고 지름길이 오히려 더 길게되는 경우도 존재한다. 또한 고속도로이므로 역주행은 불가능하다. 150이 도착지점이면 정확히 150이어야 한다. 일반 고속도로의 경우 1당 1의 거리를 지닌다. 최솟값을 찾아야 하므로 효율이 좋은 지름길을 활용해서 도착점에 도달하면 되겠다. 초기에 이차원 배열을 통해 DP로 해결하려 접근했었다. 지름길을 통하면 이전에 대한 값과 비교해서 업데이트하고, 다시 그 이후의 길을 업데이트 하는식으로 말이다. 예제는 전부 옳게되었으나 문제가 발생했다. 지름길이 겹치는 경우였다. 로직..

사고싶은 카드의 개수가 주어지고, 이 카드를 가장 비싸게 사는 방식이다. 어떻게보면 베낭문제 같다. 단순하게 작은 카드뭉치부터 구매하면서 최대값을 찾아주면 되는 문제다. 처음 문제를 볼때는 공약수를 따져서 해야하나.. 했는데 간단하게 풀리는 문제였다. HTML 삽입 미리보기할 수 없는 소스

단순 구현문제이다. 다만 어이없게 실수해서 1시간 반을 헤맸다... 열받넹 ^ 0, 데기 -> 1 큐로 사람의 위치를 구현해줬다. 물론 % 연산으로도 가능하다. HTML 삽입 미리보기할 수 없는 소스 % 연산으로 사람 확인 HTML 삽입 미리보기할 수 없는 소스

길이가 짧은 것부터 길이가 같으면 사전 순으로 1181번: 단어 정렬 간단했으나 Compare 인터페이스의 Sort를 이용할때 문자열의 길이도 고려하며 정렬해야했다. Sort 함수 Override이 필요하다고 판단했으나 사용법이 헷갈려 검색을 활용했다. 자바에서 객체를 비교하는 방법은 Comparable 인터페이스를 구현하거나 Comparator 인터페이스를 이용하는 두 가지 방법이 있다. Comparable compareTo를 활용해서 요소를 비교하는데 메서드를 통해 인자로 넘어온 같은 타입의 다른 객체와 대소 비교를 한다. 메서드를 호출하는 객체가 인자로 넘어온 객체보다 작을 경우에는 음수를 리턴하고, 크기가 동일하다면 0, 클 경우에는 양수를 리턴해야하는 특징이 존재한다. public class P..

배낭 문제이다. 초등학교때 이런유형 문제 수학시간에 나왔던거 같아 하나하나 다 따지자니 중복이 많으므로 범위를 나눠서 큰 문제를 푸는 DP를 선택했다. 배낭의 무게에 여유가 있다면 해당 물건을 담고, 이후 가방에 더이상 넣을 수 없다면 배낭 안의 물건과 가치를 비교해서 넣어주면 되겠다. 2차원 배열로 가방의 순서대로 진행하되, 무게를 저장해줬다. DP[ i ][ j ] 를 설명하면 i번째 물선 순서에 j의 무게를 담을 수 있는 가방 상황에서의 가치를 담고있다. 표로 정리해보면 무게 최대는 9Kg라 가정. W는 무게, V는 가치이다. 세로는 가방 무게인 J를 나타내고, 가로는 물건의 순서를 뜻한다. 초기에는 아무것도 들어있지 않으므로 0이다. DP[1][6] 이후로는 무게 6의 가치8 물건을 넣을 수 있으..

위치를 바꿔서 연속적인 색의 사탕을 먹는 게임이다. 모든 경우를 따져야한다 판단했고 브루트포스로 풀어봤다 가로와 세로 바꾸는 모든 경우의 수를 전부 확인해서 가장 긴 크기를 구했다. 아무것도 바꾸지 않아야 큰 경우도 존재했기에 추가했다. HTML 삽입 미리보기할 수 없는 소스