출항사

문제는 길지만 간단하게 해결할 수 있는 시뮬레이션 문제이다. 4개의 톱니바퀴가 주어지고, 특정 톱니바퀴를 회전시킬 때, 양옆에 존재하는 톱니바퀴에 영향을 준다고 한다. 회전을 모두 수행했을 때 최종 상태를 맞추면 되는 문제이다. 톱니바퀴는 시계 방향, 반시계 방향으로 회전할 수 있다. 따라서 덱 자료구조로 톱니바퀴를 구현해주면 아주 간단하게 양쪽 방향의 회전을 구할 수 있다. 그다음은 쿼리가 들어올때마다 회전시키기만 하면 된다. 초록색으로 표시된 값들이 무엇인지가 중요하기에, 이를 기준으로 비교해 주고 회전의 영향을 퍼뜨려주면 된다. 주의해야 할 점은 각 톱니바퀴가 회전할 것인지, 한다면 어느 방향인지 모두 표시를 해놓은 후 한 번에 회전을 해야 한다는 점이다. 순차적으로 회전시키면 비교할 때 잘못된 계..

간단한 다이나믹 프로그래밍 문제이다. 각 도시별로 [ 홍보 비용, 고객의 수 ] 정보가 주어진다. 이때 최소 C명을 모으기 위해 필요한 최소 비용을 구하라고 한다. 단, 도시별로 여러번 홍보할 수 있다. DP[i][j] = i번째 도시까지 j명을 모으기 위한 최소 홍보 비용이라고 정의하자. 그러면 점화식을 도출할 수 있는데, j가 i번째 사람의 고객의 수보다 크거나 같을때 DP[i][j] = DP[i][j-고객의 수] + 홍보 비용이 된다. 그리고 j가 i번째 사람의 고객의 수보다 작다면, DP[i][j] = DP[i-1][j]가 된다. 이를 2중 for문으로 구해주면 된다. 주의 해야할점은 '최소한 C명'이 되는 비용을 구하는 것이다. 따라서 j의 범위는 최댓값인 1100까지 잡고 점화식을 돌려야 한다..

정말 간단한 그래프 탐색 문제이다. 나를 기준으로 친구들과는 적대적인 관계이지만, 친구의 친구와는 우호 관계라고 한다. 이를 만족하는 그래프인지 확인해야 하는데, 그래프가 순환하는 형태인지 확인하면 된다. 왜냐면 트리 구조일 경우에는 무조건적으로 위의 조건을 만족하기 때문이다. 자 그럼 그래프가 순환하는지 확인해보자. 현재 노드와 연결된 노드 중 이전에 방문한 적이 있음에도 나와 우호적인 관계로 표시된 노드가 있다면 그래프가 순환하는 상태라고 판단할 수 있다. 그래서 boolean 변수를 하나 두고, dfs 탐색에 조건문 하나를 추가해 이를 판별하도록 구현했다. #include #define MINF 0x7f7f7f7f #define INF 1000000000 #define MOD 1000000009 #..

이분탐색 + 우선순위 큐 자료구조를 사용해야하는 문제이다. N개의 재료중 Oi가 1인 재료 K개를 제외했을때, 세균의 합이 G이하라면 먹을 수 있다. 이때 최대 유통기한을 얼마나 만들 수 있을까? 문제를 보자마자 이분탐색인걸 파악했다. mid로 날짜를 대입해보면서 만족하는 최대 mid를 구하면 되겠다 싶었다. 그러면 K개를 어떻게 선정할까? 그리디하게 생각해보고 싶지만, Si * max(1, x - Li)를 항상 보장할 수는 없다. 그래서 우선순위 큐에 현재까지 뽑은 재료 K개를 유지하도록 접근해봤다. mid를 이용해 모든 세균의 합을 구하고, 마지막에 우선순위 큐에서 K개의 재료로 인해 발생한 세균을 빼주면 간단하게 구할 수 있다. 날짜는 최대 20억이 가능하므로 left = 1, right = 2e9..

노드가 최대 4000개, 간선이 최대 4000개라는 제한이 들어온다. 여기서 3개의 노드를 선택한다. 이때 이 3개의 노드는 서로 인접한 상태여야 한다. 각 노드를 A, B, C라고 할때 A, B, C가 인접한 모든 노드의 개수 - 6의 최솟값을 구하라고 한다. 이때 노드는 중복해서 세야 한다. 4000 C 3을 하기에는 제한이 조금 빡세기에 더 쉬운 방법을 생각해봐야 한다. 우선 각 노드별로 자신이 인접한 노드의 개수를 구하는 것은 어렵지 않다. 이 값을 활용해보자. A, B, C를 동시에 선정하기에는 아무리 생각해도 너무 빡빡하니, A만 먼저 구해보자. 그러면 A와 인접한 노드들 중에 B, C가 모두 존재해야 한다. 자 그럼 B를 하나 뽑아보자. C를 선정하기 위해서는 자신과 인접하고, A와 인접한 ..

처음에 문제를 잘못이해해서 맞왜틀을 했다. 구하고 싶은 값을 아주 간단하게 정의하면 초기의 잔디 상태가 주어졌을때, 결과로 주어진 잔디 상태를 만들 수 있는가?를 묻고 있다. 처음 주어지는 잔디를 graph, 최후의 잔디를 result라고 일단 정의를 했다. 만약 graph에서 O인데 result에서 X인 상태가 주어진다면 절대 만들 수 없다. 나는 이 부분을 놓쳤고 O를 전부 채우기만 하면 된다고 문제를 접근해 자꾸 틀렸다. 이 부분을 고려했다면 이제 result 잔디를 만들 수 있는지 확인해야 한다. 나는 BFS와 DFS를 적절히 섞어 문제를 해결했다. 먼저 초기 잔디를 기준으로 BFS를 돌릴것이다. 근데, 최대 D만큼 이동해 잔디를 채울 수 있다. 이때 지나간길을 전부 잔디로 채우지 않아도 된다. ..

여러 가지 자료구조를 사용해야 하는 문제이다. 먼저 제한을 자세히 살펴보고 문제를 해석해 보자. 지하철 노선의 개수는 10개뿐이다. 그리고 이 노선에 속하는 역이 입력으로 들어온다. 이때 역의 값은 최대 2^32-1까지 가능하다. 반면 역의 개수는 최대 10*10이 될 수 있다. 각 역에 도착하기 위한 최소 비용을 배열로 나타내기 위해서는 역을 압축해야 한다는 것을 알 수 있다. 따라서 0 ~ 2^32-1의 범위에 속하는 역들을 0 ~ 100에 해당하는 값으로 치환하는 작업을 수행하자. 결국 구하고 싶은 것은 몇 번 지하철을 갈아타는지이다. 따라서 지하철을 기준으로 도달할 수 있는 역들에 전부 방문을 표시하고, 역에서 환승할 수 있다면 환승을 하면 된다. 이때 방문 값이 1 증가하게 되고 우리는 이 값의..

프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 간단하게 생각해보면, 매우 쉬운 문제이다. N까지 도달하고 싶은데, 2배씩 건너뛸 수 있다고 한다. 그리고 1칸씩 이동할 수 있는데, 1칸씩 이동하는 횟수를 최소로 만들고자 한다. 뒤에서부터 생각해보자. N = 1000일때, 가장 이득인 방법은 N = 500에서 2배로 뛰는 방법일 것이다. 그리고 N = 250 에서 500으로 뛰고 ... 이러다 보면 N = 125에서 막히는데, 홀수이기 때문이다. 그래서 1칸 이동했다 치고, N = 124부터 보자. 이런식으로 N = 0이 될때까지 확인하면 된다. 간단하게 ..