프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr 해결하는데 좀 오래 걸렸다.처음에는 구현, 그리디 방식으로 해결이 가능할 것 같다고 생각했지만 실패했다.1. 원형으로 이루어진 외벽을 일직선으로 편 후, 길이를 2배 늘린다.2. 점검할 수 있는 거리를 내림차순으로 정렬.3. 각 친구가 점검할 수 있는 만큼 최대한의 취약 지점을 찾아 처리.이런 방식으로 가능할 것이라 생각했지만,'점검 거리 내에 포함되는 취약 지점의 수가 같은 경우가 2개 이상 생기면 어떤 구간을 선택해야 하는가'를해결할 수 없어서 다른 방법을 고민했다. 결론적으로 백트래킹을 써서 해결. 1. 취..
전체 글
https://www.acmicpc.net/problem/10800 공의 개수가 최대 20만 개, 색상 수도 최대 20만 개, 크기는 최대 2천 가지라 어떻게 해결해야 할지 고민을 좀 많이 했다.크기 순으로 정렬을 하더라도, 같은 색상의 공들은 빼야 하고, 같은 크기를 가지는 공들도 제외해야 한다. 이를 해결하기 위해 같은 색상 공들의 크기 합, 같은 크기를 가지는 공들의 크기 합을 따로 보관해야겠다고 생각했다.같은 색상 공들의 크기를 따로 보관하면, 전체 공 크기의 합에서 같은 색상 공들의 크기 합을 빼 해당 공의 점수를 구할 수 있게 된다.같은 크기를 가지는 공은 순회하면서 앞의 공과 크기가 달라질 때마다 비워주면서 전체 공의 크기 합, 같은 색상 공들의 크기합을 누적하도록 했다. 로직 순서1. 색..
2655번: 가장높은탑쌓기첫째 줄에는 입력될 벽돌의 수가 주어진다. 입력으로 주어지는 벽돌의 수는 최대 100개이다. 둘째 줄부터는 각 줄에 한 개의 벽돌에 관한 정보인 벽돌 밑면의 넓이, 벽돌의 높이 그리고 무게가 차www.acmicpc.net 문제를 보고 생각난 풀이는 백트래킹, 추적할 수 있는 DP 두 가지였다.하지만 벽돌의 수가 최대 100개이기 때문에 백트래킹으로 풀이할 경우 시간 초과가 날 것이라 제외했다. 문제 조건을 보면, 각 벽돌의 밑면 넓이와 무게는 모두 다르다.나는 무게를 기준으로 삼아 내림차순으로 벽돌을 정렬했다. DP 테이블을 만들어가며 추적까지 가능하도록 pair를 사용해서 테이블을 만들었다.std::pair dp[101]; // {total_height, from} DP[..