본문 바로가기

매일 알고리즘 2문제

2294 동전2 이 문제는 앞서 풀었던 동전1과 모든 경우의 수를 구하는지, 최소의 개수로 K를 이룰 수 있는지 의 조건만 바꾸어주면 쉽게 풀 수 있다. 단, 이 문제의 경우 이룰 수 없는 경우가 있다는 것을 전제로 하기 때문에 처음 배열 생성시 -1로 초기화 해 주어 최종적으로 이룰 수 없는 경우 -1로 출력해주는 것이 바람직하다. 기존 동전1 방식에서 수정해준 부분은, 해당 동전의 개수로 판단해야하기때문에 1) 기존에 dp[j] += dp[j-코인] 였던 점화식을 dp[j] = dp[j-코인] + 1 과 같이 개수를 늘려주는 것과 2) 현재 배열에 이미 값이 존재한다면, 기존의 값과 비교하여 MIN 값을 판단한다. 소스코드는 아래와 같다. (dp[0] = 0 을 해주어야 하는 이유는 초기 동전값을 넣어주기 위함이다... 더보기
2293 동전1 올림픽과 설연휴에 빠져 놀기만하고ㅠㅠ, 이제서야 업로드한다. 이번에는 쉬운 DP에 속하는 동전1문제를 풀어볼건데 우선 주어진 동전의 개수(N) 가 최대 100이고, 원하는 값(K) 가 10000 이므로 완전탐색으로 구했을 경우에 시간초과가 나지 않는다. 단, 여기서는 DP임을 알고 1. 점화식을 구해야 하는 문제인지 2. 점화식을 구하지 않고 풀 수 있는 문제인지 를 판단해야 한다. 필자의 주관적인 입장이므로 필자의 경우 점화식을 구하지 않고 푸는 문제의 경우 재귀식을 사용한다. (아직 알고리즘 초보이므로 단언할 수 없다!) 이 문제의 경우 아래 그림과 같이 300원의 원하는 값을 만들기 위해 주어진 동전이 100, 200이라면 100원을 3개 사용하는 방법과 100원+200원을 사용할 수 있는 총 2가.. 더보기
10431 줄세우기 어려운 문제를 푸려다가, 모르는 알고리즘에 부딫혀 한동안 쉬운 문제만 또 풀게되었다..ㅠㅠㅠ 이번에는 조금 어려운 문제 해설을 올리고 싶었으나, 우선은 ACM 기출문제 (이것도 정답률 높은 문제) 를 올린다. 줄세우기는 같은 이름의 다양한 문제가 많은데, 이번 문제의 경우 기본 규칙? 정도만 알면 쉽게 접근할 수 있는 문제이다. 우선 현재 자신의 위치보다 앞에 키가 큰 학생이 있다면 바꾸어주어야 하기 때문에 정렬알고리즘을 생각하면 비교적 짧은 코드에 구현 가능할 것이라 생각한다. #include int T,num[21],N; int main() { scanf("%d", &T); while(T--){ int sum = 0; scanf("%d", &N); for (int i = 0; i < 20; i++) .. 더보기
1002 터렛 정답률이 굉장히 낮음에도 불구하고, 고등학교 때 ' 두 원의 교점 구하기' 문제를 풀어봤던 사람이라면 풀 수 있는 문제이다. 참고로 문제를 보고, 바로 원을 떠올릴 수 있어야 하고 필자의 경우 고등학생 시절 풀었던 SSEN 을 참고하여 구현해보았다. 규칙을 아래와 같이 5개의 규칙으로 나누어질 수 있는데 1. 한 원 안에 다른 원이 포함되 있는 경우 => 이 경우 내접하는지, 내접한다면 두원사이의 반지름길이가 같은지에 따라 세부적으로 나누어질 수 있다. 2. 두 원이 포함관계는 성립하지 않지만, 2개의 교점이 있는 경우 3. 두 원이 포함관계는 성립하지 않지만, 1개의 교점이 있는 경우 4. 포함관계도 성립하지 않고, 교점 또한 없는 경우 어떻게보면 5가지로 나누어질 수 있으나, 그림을 통해 설명해보겠다.. 더보기
10426 기념일2 이 문제도 평년, 윤년만 잘 구별하면 쉽게 풀 수 있는 문제이다. 평년 윤년은 미리 일 수를 세어 배열로 만들어 두고,2월에만 윤년의 경우 29, 평년의 경우 28로 세면 되므로비교적 간단하게 배열을 통해 계산가능하다. 필자의 경우 처음 100의 배수가 아니거나 또는 400의 배수 라는 조건에서 '또는' 을 '그리고' 로 착각하여 오답률을 높였지만, 이 글을 읽고 계신 분들은 한번에 맞추시리라 믿는다! 이번 문제는 정답률도 낮지 않고, 규칙을 알면 금방 풀 수 있는 문제기에 소스코드는 패스하도록 한다.! 더보기
3231 카드놀이 이 문제는 규칙성을 생각해보면 풀 수 있는 문제로,여러개의 (N개의) 카드를 탐색해가며 가장 오른쪽 끝에서 왼쪽으로, 즉 한쪽 끝까지 탐색을 완료했을 때를 count 해주는 문제이다. 처음에 N개의 카드에 각각의 위치를 저장하고, 현재 count 해야하는 카드가 다음 count해야 하는 카드의 위치보다 오른쪽에 있다면한쪽 끝까지 탐색 후 다시 가장 왼쪽으로 돌아가 탐색을 시작해야 하기 때문에 이 경우에 cnt(박수 횟수) 를 증가시키면 된다. 예시로 3 2 5 4 1의 경우를 들어보자면, 우선 1과 2를 탐색하는 것만 간단한 그림으로 나타내 보았다.1을 탐색 후 왼쪽 끝으로 돌아와 다시 2를 탐색해야 하기 때문에 박수를 한 번 친 후에 왼쪽 끝으로 이동해야하므로이 과정에서 cnt가 1증가하게 된다. 같은.. 더보기
4153 직각삼각형 이 문제를 쓰면서도 양심에 좀 찔리지만! (오늘은 2문제다 기본적인 문제이다....ʘ̥_ʘ) 사실 이 문제는 피타고라스의 정리를 아는 사람이라면 풀 수 있는 문제이다. 피타고라스의 정리 : 빗변의 길이의 제곱은 다른 두 변의 제곱의 합과 같다. 여기서 빗변은, 세개의 변 중 가장 긴 변을 의미한다. 따라서 아래와 같은 공식이 정의되고, 이를 활용해서 소스코드로 옮겨 작성하면 된다. 더보기
5347 LCM 기본 알고리즘에 올려놓은 GCD 에 관련된 문제이다.GCD 알고리즘을 그대로 이용하면 되므로, 구체적인 설명은 생략하도록 하겠다. #include long long T,a,b; long long gcd(const long long &a, const long long &b) { return a%b ? gcd(b, a%b) : b; } int main() { scanf("%d", &T); for (int i = 0; i < T; i++) { scanf("%lld%lld", &a, &b); printf("%lld\n", a*b/gcd(a, b)); } return 0; } 더보기
8741 이진수 합 이문제는 조금 황당..?하다고 해야하나 규칙을 찾으면 의외로 간단하게 풀리는 문제다 필자는 이 문제를 deque + 이진수배열 을 만들어서 풀려고 하다보니 계속된 메모리 초과가 발생했다. (메모리 초과에 대해서는 '기본알고리즘' 카테고리에 어떻게 계산하는지 추후에 올려놓을 생각이다.) 처음에 주어진 테스트케이스 3을 가지고 계산해본 결과가 11100 따로 5, 7, 9 ... 2씩 늘려가며 계산해본 결과 5 -> 111110000 7 -> 1111111000000 9 -> 11111111100000000 규칙을 이미 발견하신 분도 계시겠지만, 이 문제는 규칙성에 관한 문제이다. 한마디로 주어진 k값에 대해서 처음 1은 k만큼, 0은 (k-1)만큼 출력되어야 한다. #include int k; int ma.. 더보기
1421 나무꾼 이다솜 이 문제는, 생각보다 완전탐색을 이용해서 시간초과가 나지 않고 풀 수 있는 문제임에도 정답률이 꽤 낮다. N의 범위가 1000이고, N의 하나의 값이 10000임을 고려하였을 때 최악의 복잡도를 생각해보아도 10000000이 나오기 때문에 완전탐색 즉 브루트포스 방식으로 구현이 가능하다. 우선 처음에 고려하지 못하였던 부분에 대해 다들 고민하실 것 같아 써보자면, 나무가 N개 존재하지만 모든 나무를 사용할 필요는 없다. 그 중 일부만 파는 것 또한 가능하다. 처음에 이 부분을 고려하지 않아서 여러번 시도 끝에 성공하였다. 자르는 비용이 커서 총 합계가 음수가 나오는 경우 그 나무도막을 과감히 버려야 할 것이다. 이 문제를 요약해보자면, 1) 나무도막 한 단위의 가격과 자르는 비용을 비교하여 고려해볼것. .. 더보기

티스토리툴바