jihyung1997

아이디어만 생각해두고 언젠가 풀려고 했는데 백준이 서비스 종료한다고 해서 아이디어만이라도 적어두려고 한다.. 구현하고 수많은 디버깅을 뚫기에는 이제 알고리즘 문제 풀 시간이 없을 것 같다...이 문제를 풀 때 수많은 아이디어가 떠올랐던 것 같지만 현재 가장 유력한 아이디어는 다음과 같다.우선 위와 같이 소방차를 1번부터 맨왼쪽 호스로 차례로 연결한다. 그럼 모든 소방차는 왼쪽 호스로 쏠린 상태일 것이다.그러나 그런 상태는 절대로 정답이 아닐 것이다. 그렇다면 위와같은 상태에서 소방차와 호스사이에 칸을 띄워야 할 것이다. 예를들어 소방차 2번부터 한칸을 띄우면 아래와 같이 된다.위와 같은 상태를 편의상 아래와 같이 나타낸다 치자.즉 1번소방차, 2번소방차 사이의 1의 의미는 1번과 2번사이에 1칸을 ..

https://www.acmicpc.net/problem/18444 아이디어도 어려웠고, 특히 한번도 구현해보진 않은 희소배열의 아이디어를 기억 깊숙한 곳에서 꺼내기가 힘들었다.. + 구현도 상당히 복잡했고,, 제일 큰 이슈는 java로는 시간제한을 지킬 수 없는 문제여서 수없는 삽질을 하였다...Wow 처음 생각한 아이디어는 누적합을 이용한 dp 였다. 위와 같이 dp는 시작지점, 끝지점, 그 사이의 우체국 갯수 (시작 , 끝 점은 우체국 반드시 포함) 을state로 한다. dp[2][6][3] = Math.min(dp[2][5][2], dp[2][4][2], dp[2][3][2]) 의 점화식을 가질 것이다.end 지점이 e번이고 시작지점이 s번, 우체국 갯수가 p개인 dp를 구하고자 할 ..

https://www.acmicpc.net/problem/32115 아무리 봐도 플레3은 아닌 문제였다. 아이디어 발상도 흔하지 않아 떠올리기 어렵고, 구현도 내 기준 쉽지 않았다.. 게임이론에서 쓰이는 이상한 알고리즘이 있는데 그 알고리즘이면 안 푸려고 분류를 확인하였다.. (보면서 얼떨결에 그리디라는 것도 알게 되어 큰 힌트가 된듯)위와 같은 경우를 생각해보자. (초록색: 점수 검정색: 흑or백) 흑 과 백이 번갈아 가며 자기의 색깔과 인접한 빈칸에 둘때 다음과 같은 생각은 어렵지 않게 할 수 있다. 같은 색깔이 둘러싸고 있는 구간은 다른 색깔이 침범할 수 없다.위와 같이 묶인 그룹에는 다른 색깔이 침범할 수 없다. 예를 들어 2번 그룹 (백으로 둘러싸임)에 흑이 들어갈 수 없다. 백은 백끼리 흑..

https://www.acmicpc.net/problem/2315경계값을 잘 생각하고, 누적합 적용하면 그렇게 어렵진 않았었던 dp문제다. 우선 마징가가 어떤 경향을 가지고 움직일지 생각해보자.시작점에서 왼쪽으로 갔을 때 두가지 방법이 있다.1. 왼쪽이동(파란색)2. 오른쪽이동(초록색) : 이미 지나온 시작점에서 멈추는 것은 의미없다. 즉 아래 경우는 고려하지 않는다. 켜진 불을 끄러가야 하기 때문에 이미 꺼진불은 고려할 필요가 없다. 따라서 켜진불이 있을 때까지 , 즉 오른쪽으로 5번까지 이동한다. (위에서 처럼) 그다음 2번에 있을 경우, 아래와 같이 1번 또는 5번으로 이동할 것이다. 간단히 보면 한번 움직일 때마다 켜진 불이 있을 때까지 좌 또는 우로 이동한다고 볼 수 있다 ! 또한 현재위치는 ..

https://www.acmicpc.net/problem/24515소마 면접 준비로 너무 바빠서 브론즈로 스트릭을 연명하였고... 드디어 면접이 끝나 문제풀이를 시작할 수 있게 되었다.나름 면접에서 내 장점을 어필하려고 최선을 다했고, 워낙 대단한 분들이 많기 때문에 결과가 어떻든 납득할 수 있을 것 같다... 매우 특이한 다익스트라 문제였다. 처음엔 dp 인줄 알고 경계값 문제로 고민했지만... 생각해보니 다익으로 간단히 (구현은 힘들지만) 해결 가능하다. 우선 R은 좌측 맨위, J 는 우측 맨아래에 있는데 이둘을 못만나게 하려면 어떻게 이어야 할까? 파란 집합 중 아무 점에서 시작하고, 빨간 집합 중 아무 점으로 도착하면 무조건 R , J 를 나눌 수 있다. 그렇다면, R , J 를 나눌 수 있..

아이디어도 쉽지 않았고, 무엇보다 멍청한 판단으로 구현에서 심각하게 고생한 문제였다. 소마 면접 준비가 한창인데 왜 이걸 붙잡고 있었을까... ㅋㅋㅋ 우선 아이디어를 생각해보자. N 이 10000000이라는걸 보자마자 원형 애드훅?이라는 건 직감했는데, 이걸 어떻게 해결할지 생각하는게 쉽지 않았다. (사실 순수 애드훅도 아니였다) 우선 선물을 배달할 때 한바퀴를 돌지, 반바퀴 (N / 2)되는 지점 전 까지만 돌고 다시 돌아갈지 구분해야 겠다는 생각은 금방 들었다.그 이유는 어렵지 않다. 우선 반바퀴 이상을 도는 순간, 밑 처럼 시계방향 으로 순회할 때 5번까지 갔다면, 다시 반시계로 돌아가는 것보다(파란색) 그대로 시계방향으로 한바퀴(초록색) 으로 도는게 빠르기 때문이다. 그럼 만약 한바퀴를 한번..

이 문제는 플레 3치곤 생각보다 쉬웠다. 비트마스킹 + 브루트포스로 접근이 가능하기도 하고 (최대 열크기가 5이하이기 때문)그리디하게 K에 따라 항목별로 무엇을 택할지 정하면 되기 때문이다.우선 K = 5일때 생각해보자.4 230 30 30 30 050 0 0 0 00 50 0 50 100 0 50 0 20다음과 같은 경우 1열 ~5열까지 돌면서 그대의 최댓값일때의 행의 장비를 선택하면 된다. 만약 1열, 4열이 둘다 그 열에서 최댓값이면? 개의치 않아도 된다. 2열, 4열 이 최댓값이라, 1,3,5열에서 각각 장비를 하나씩 선택하면 장비를 4개 선택했는데, 이때가 최대이므로, 나머지 한개는 아무거나 선택하면 된다.그럼 K > 5 일 경우엔? K= 5일때도 최댓값을 선택할 수 있는데 K > 5 일땐 ..

재미있는 우선순위 큐 문제였다.사람마다 최저 임금 Si와 기술 비용 Qi 가 있을 때 , Qi * K 를 했을 때 최저임금을 넘어야 한다.그런데, 모든 사람에게는 K가 같아야 한다. 각 사람마다 Ki = Si / Qi 라고 하면, 그 사람의 비용 >= Qi * Ki = Si 가 되어야 한다. 각 사람마다 Ki가 다를 수 있는데, 이 문제에선 K가 모든 사람에게 동일하게 적용되어야 한다.Qi * K = i번째 사람의 비용 이기 때문이다. 즉 모든 사람에겐 동일한 K값이 주어지므로, K는 뽑은 사람중 K값이 가장 큰 사람의 값이어야 한다. 위와 같은 예시가 있을 K는 3.5가 될 것이다. K가 3.5보다 작으면 사람3의 최소비용이 충족되지 않기 때문이다. 즉 사람을 뽑았을 때 뽑은 사람들의 ..

이 문제의 어려운 점은 어떻게 처음에 잘 시작해서 다익스트라를 한번만 돌려 끝낼 것이냐 이다. 마지막 열은 어떤 행이든 , 도착만 하면 끝나므로 마지막 열들의 점들을 (1,4) (2,4) ... 한점으로 생각해도 될 것이다.따라서 마지막 열부터 시작해서 (1,1), (2,1) (3,1 ).... (N, 1)들에 도착할때의 최단 경로들을 카운트하면 다익스트라를 한번만 돌려도 될 것이다. 또한 마지막열에서 그 전열까지의 경로는 초록색 경로는 되지만, 빨간색 경로는 불가능 하다. (1,4)에서 시작하던 (3,4)에서 시작하던, 상관 없는데 굳이 (3,4) 에서 (2,4) -> (1,4) -> (1,3) 을 거쳐가며 구할 필요는 없다.따라서 다음그림과 같이 나타낼 수 있다.다음과같이 (2,5,8,10 ) 을 하..

재밌는 다익스트라 활용 문제였다.다익스트라의 그리디한 성질을 잘 활용하면 아이디어를 떠올리기 어렵지 않을 것이다.아이템 조합은 두가지를 조합해 한개를 만드는 것인데, 아이템1 + 아이템2 = 아이템3이라면 아이템3 가격은 아이템1가격 + 아이템2 가격 인 셈이 될 것이다.그리디하게 접근하자면, 우선 각 아이템마다 원래의 아이템 가격이 있고, 이제 그 아이템들 끼리 조합해 만든 아이템의 가격중 최소를 구한다.즉 우선순위큐에 아이템들을 합친값이 원래 가격보다 작다면, 새로운 아이템을 넣는다.그렇게 아이템들을 우선순위큐에 넣은후, 우선순위큐에서 poll 하면 그게 새로 업데이트된 아이템 가격중 최소의 가격이 될 것이다. 다음과 같이 큐에서 poll한 값이 1번이면, 1번이 지금 합성할 수 있는 아이템 ..