🔗 문제 링크 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 💡 문제 풀이 및 해석 매 skill마다 board를 바꾸면, 시간복잡도가 너무 증가한다. 따라서 매번 바꾸는 방식은 안된다. 여기서 누적합 혹은 DP방식으로 풀어야 한다는 것을 알 수 있다. 여기서 2차원 배열에서의 누적합으로 풀어야 하는데, 풀이 방식은 각 모서리에 마킹을 해두는 것이다. Attack 기준으로 아래 코드에서도 볼 수 있듯이 4x4 사이즈에서는 5x5 사이즈의 임시 맵의 모서리에 마킹을 해둔다. MAP[r1][c1] -= degree; MAP[r1][c2 + 1] += degr..
Lv.3
🔗 문제 링크 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 💡 문제 풀이 및 해석 최악의 경우 모든 금(10^9)+은(10^9) 을 10^5*2 만큼 움직여야 하므로 400조의 시간이 걸린다. 이는 일반적인 방법으로는 해결할 수 없고, "이분탐색"과 같은 방식으로 해결할 수 있을 것으로 보인다. 하지만, 어떤 조건이 성립해야 모두 시간안에 옮길 수 있을까? 라는 조건은 쉽게 생각나지 않는다. (저도 이 부분은 구글링을 했습니다.) 최대로 옮길 수 있는 금의 양 >= a && 최대로 옮길 수 있는 은의 양 >= b && 금+은 통합해서 최대로 옮길 수 있..
🔗 문제 링크 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 💡 문제 풀이 및 해석 직사각형의 크기만큼 모두 더하면 최악의 경우 $$1000\times1000\times250000$$ 이라는 말도안되는 경우의 수가 발생하므로 다른 방법을 생각해야 한다. 여기서 DP 아니면 누적합이 보통은 떠오를 텐데, 솔직히 문제 후기에서 말한듯이 둘 중 하나를 선택하고 생각하는 것은 개인의 능력이 아닐까 싶다. 이 문제는 제목에 써놓은 듯이 누적합 문제이다. 일차원 누적합이 아닌 2차원 누적합이니 다른 방법이 필요한데 아래 만약, (0,0) (2,2) 에 5를 더한다고..
🔗 문제 링크 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 💡 문제 풀이 및 해석 1. 10000명정도의 사람이 들어올 수 있는데, 각각의 사람이 판매 금액의 10%씩 추천인에게 주어야한다. 2. 여기서 12원일때 1.2원이 되는게 아니고 1원씩 올라가는 것을 보니 int / 10 형식으로 올리는 것 같다. 3. 단, A->B 에서 12원을 주고, C->B 에서 18원을 줄 때, 따로따로 주면 B->D 에서 각각 1원씩 주지만, 이 계산을 한번에 진행한다면 ( 12+18 ) / 10 = 3 이 되므로 각각 계산해야 한다. 4. 0원일 때, 추천인이 없을..
