본문 바로가기

Programming456

#1214 쿨한 물건 구매(정수론) 이번 문제는 정수론을 잘 이해하셔야 풀기 편한 문제입니다. 보통 확장 유클리드 소거법이라는 것을 이용하게 되는데요. 확장 유클리드 소거법은 두개의 수가 주어졌을 때, 유클리드 소거법을 이용해서 최대공약수를 구하는 과정을 거꾸로 하는 것입니다. 예를 들어서 12와 20의 최대공약수를 구하는 과정을 볼께요. \[ 8 = 20 - 12 \] \[ 4 = 12 - 8 \] 로 12와 20의 최대공약수는 4임을 알 수 있습니다. 그리고 이 식을 거꾸로 가게 되면, \[ 4 = 2 \times 12 - 20 \] 을 얻을 수 있죠. 이렇게 최대공약수를 구하는 파라미터터 (2, -1)을 얻는 것이 확장 유클리드 소거법의 목적입니다. 아래의 소스는 확장 유클리드 소거법을 프로그램한 것입니다. void xgcd(long.. 2020. 1. 7.
백준 #1202 보석 도둑 이번 문제는 knapsack 문제라고 볼 수 있는데, 전혀 다른 문제네요. 그래도 탐욕 알고리즘을 적용하기 위해서 방법을 강구해야 합니다. 난이도는 Gold II 문제입니다. 정답률 23%로 상당히 낮습니다. 왜 틀릴까 생각했었는데, 틀린 이유들을 보면, 짐작이 갑니다. K개의 가방에 보석을 1개씩만 넣을 수 있는데, 각 가방에는 최대 넣을 수 있는 보석의 무게가 정해져있습니다. 보석에 무게와 값이 주어질 때, 가장 값어치가 높게 보석을 챙겨올 때, 그 값어치를 구하라는 문제입니다. https://www.acmicpc.net/problem/1202 1202번: 보석 도둑 문제 세계적인 도둑 상덕이는 보석점을 털기로 결심했다. 상덕이가 털 보석점에는 보석이 총 N개 있다. 각 보석은 무게 Mi와 가격 Vi.. 2020. 1. 6.
백준 #1194 달이 차오른다, 가자 이번 문제는 재미있는 문제였다고 봅니다. 스토리가 있긴 한데요. 난이도는 Gold I입니다. 정답률 25.9%, 정답자 1,001명입니다. 한지민이 인생의 미로를 탈출하려고 합니다. 자신이 처해있는 상황을 해결하기 위해서는 탈출구로 탈출해야 합니다. 그런데, 간혹 해결할 수 없는 문제에 도달합니다. 이 문제를 해결하기 위해서는 키를 구해야 하는데, 키는 그 문제에 맞는 키여야 해당 문제를 해결할 수 있습니다. 키는 a~f까지 존재하며, 문제는 A~F까지 존재하고, 각각이 대응되는 키와 문제입니다. 해결할 수 없는 문제는 #입니다. 0은 출발점이고, 1은 새로운 탈출구입니다. 봄이 가기전에 가장 빨리 탈출구로 탈출하려고 합니다. 늙어서 김혜자가 되면 안 되거든요. 문제는 전형적인 BFS 알고리즘 문제에서 .. 2020. 1. 6.
백준 #1153 네 개의 소수 골드바흐의 추측과 관련해서는 한두번 이상은 들어보았을겁니다. 유명한 문제이긴 하지만 아직 증명이 안 되었죠. 사실 수학적 가치가 크다고 볼 수는 없는 문제입니다. 쉽게 증명될 것이라는 예상과는 달리 아직까지 미해결 문제입니다. 골드바흐의 추측은 2보다 큰 수는 세개의 소수의 합으로 만들 수 있다였습니다. 사실 당시에는 1이 소수로 취급되었을 때였기 때문에, 3=1+1+1, 4=2+1+1, 5=2+2+1 로 표현이 가능했습니다. 현대 소수 개념으로는 6이상의 수는 세개의 소수의 합으로 표현할 수 있다입니다. 이번 문제는 Gold IV 난이도입니다. https://www.acmicpc.net/problem/1153 1153번: 네 개의 소수 임의의 자연수가 주어지면, 이를 네 개의 소수의 합으로 분해하는 프.. 2020. 1. 5.
백준 #1149 RGB 거리 이번 문제는 일렬로 늘어선 집들이 있을 때, 여기에 빨강, 초록, 파랑색으로 집을 색칠하는 것입니다. 색마다 칠하는 비용이 집마다 주어지고, 이웃간에는 색을 달리 칠해야 합니다. 최소의 비용으로 칠을 할 때, 그 비용은 얼마인 가입니다. 문제의 난이도는 Silver I 문제입니다. 정답률도 47.2%로 적당한 수준의 문제입니다. 기초적인 알고리즘 지식만 있으면 풀 수 있는 문제입니다. https://www.acmicpc.net/problem/1149 1149번: RGB거리 RGB거리에 사는 사람들은 집을 빨강, 초록, 파랑중에 하나로 칠하려고 한다. 또한, 그들은 모든 이웃은 같은 색으로 칠할 수 없다는 규칙도 정했다. 집 i의 이웃은 집 i-1과 집 i+1이고, 첫 집과 마지막 집은 이웃이 아니다. 각.. 2020. 1. 5.
백준 #1141 접두사 이번 문제는 접두사문제입니다. 문제의 뜻을 잘 해석 해야 하는데, 접두사 X 집합이라는 뜻을 잘 이해하셔야 합니다. 난이도는 Silver I이며, 정답률은 44.6% 정도입니다. 난이도는 보통이면서 예외가 많지 않은 편입니다. 문제 링크입니다. https://www.acmicpc.net/problem/1141. 1141번: 접두사 접두사X 집합이란 집합의 어떤 한 단어가, 다른 단어의 접두어가 되지 않는 집합이다. 예를 들어, {hello}, {hello, goodbye, giant, hi}, 비어있는 집합은 모두 접두사X 집합이다. 반면에, {hello, hell}, {giant, gig, g}는 접두사 X 집합이 아니다. 이때, 단어가 N개 주어질 때, 이 단어의 부분 집합 중 접두사X 집합이면서 크.. 2020. 1. 5.
728x90

티스토리툴바