[파이썬] 백준 11047 : 동전 0

[파이썬] 백준 11047 : 동전 0

[파이썬] 백준 11047 : 동전 0 https://www.acmicpc.net/problem/11047 11047번: 동전 0 첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 10, 1 ≤ K ≤ 100,000,000) 둘째 줄부터 N개의 줄에 동전의 가치 Ai가 오름차순으로 주어진다. (1 ≤ Ai ≤ 1,000,000, A1 = 1, i ≥ 2인 경우에 Ai는 Ai-1의 배수) www.acmicpc.net 실버 3 그리디 알고리즘 접근 실버 3이라 하기에는 쉬운 문제였다. 아무래도 그리디 알고리즘 문제가 전반적으로 구현 난이도가 쉬운 편이라서 그런 듯. 반복문을 거꾸로 돌리는 방법으로 동전의 단위를 큰 순서대로 순회할 수 있다. 해당 동전이 만들려는 K원보다 클경우는 다음 동전 단위로 차례를 넘기..

  • format_list_bulleted 알고리즘 문제 풀이
  • · 2022. 3. 5.
  • textsms
[파이썬] 백준 2217 : 로프

[파이썬] 백준 2217 : 로프

[파이썬] 백준 2217 : 로프 https://www.acmicpc.net/problem/2217 2217번: 로프 N(1 ≤ N ≤ 100,000)개의 로프가 있다. 이 로프를 이용하여 이런 저런 물체를 들어올릴 수 있다. 각각의 로프는 그 굵기나 길이가 다르기 때문에 들 수 있는 물체의 중량이 서로 다를 수도 있다. 하 www.acmicpc.net 실버 4 수학, 그리디 알고리즘, 정렬 접근 최대 중량이 각각 10, 15인 로프가 들 수 있는 물체의 최대 중량은 10x2 = 20이다. 15가 최대인 밧줄은 15를 들 수 있지만 10이 최대인 밧줄은 10까지 밖에 들 수 없다. 따라서 10 밧줄을 기준으로 생각한다면 10x2 = 20이 들 수 있는 최대 중량이며, 15 밧줄을 기준으로 생각한다면 15..

  • format_list_bulleted 알고리즘 문제 풀이
  • · 2022. 3. 5.
  • textsms
[파이썬] 백준 1026 : 보물

[파이썬] 백준 1026 : 보물

[파이썬] 백준 1026 : 보물 https://www.acmicpc.net/problem/1026 1026번: 보물 첫째 줄에 N이 주어진다. 둘째 줄에는 A에 있는 N개의 수가 순서대로 주어지고, 셋째 줄에는 B에 있는 수가 순서대로 주어진다. N은 50보다 작거나 같은 자연수이고, A와 B의 각 원소는 100보다 작거 www.acmicpc.net 실버 4 (이게 왜 실버4까지나?) 수학, 그리디 알고리즘, 정렬 접근 곱하기를 할때 가장 작은 값이 나오려면 작은 수는 큰 수와 서로 곱하도록 하면 된다. 그냥 단순하게 A는 오름차순, B는 내림차순해서 서로 곱하면 좋겠지만 B는 재배열 하지 말랬으니 B의 최댓값을 계속해서 갱신하는 방법으로 문제를 풀었다. 코드 풀이 import sys input = s..

  • format_list_bulleted 알고리즘 문제 풀이
  • · 2022. 3. 5.
  • textsms
[파이썬] 백준 5585 : 거스름돈

[파이썬] 백준 5585 : 거스름돈

[파이썬] 백준 5585 : 거스름돈 https://www.acmicpc.net/problem/5585 5585번: 거스름돈 타로는 자주 JOI잡화점에서 물건을 산다. JOI잡화점에는 잔돈으로 500엔, 100엔, 50엔, 10엔, 5엔, 1엔이 충분히 있고, 언제나 거스름돈 개수가 가장 적게 잔돈을 준다. 타로가 JOI잡화점에서 물건을 사 www.acmicpc.net 브론즈 2 그리디 알고리즘 접근 그리디 알고리즘의 가장 기본적인 문제이다. 거슬러야하는 돈을 단위가 큰 순서대로 리스트에 담고, 몫과 나머지를 적절히 활용하면 쉽게 구할 수 있다. 그리디 알고리즘은 최적의 해를 빠르게 구하기 위해 현재 상황에서 당장 좋은 것만 고르는 방법이다. 코드 풀이 import sys coins = [500, 100..

  • format_list_bulleted 알고리즘 문제 풀이
  • · 2022. 3. 5.
  • textsms
[파이썬] 백준 1837 : 암호제작

[파이썬] 백준 1837 : 암호제작

[파이썬] 백준 1837 : 암호제작 https://www.acmicpc.net/problem/1837 1837번: 암호제작 원룡이는 한 컴퓨터 보안 회사에서 일을 하고 있다. 그러던 도중, 원룡이는 YESWOA.COM 으로부터 홈페이지 유저들의 비밀키를 만들라는 지시를 받았다. 원룡이는 비밀 키를 다음과 같은 방법으로 www.acmicpc.net 브론즈 3 (이게 왜 브3??) 수학, 브루트포스, 큰 수 연산 접근방법 어떤수를 소인수분해하면 소수들의 곱으로 표현할 수 있다. 그 소수들 중 가장 작은 값이 K보다 작은지에 대한 여부를 확인해야 한다. 시행착오가 너무 많았다. p와 q가 소수라는 것 때문에 소인수분해를 하도록 했는데 시간초과가 계속해서 났다. 문제에서 요구하는 것은 입력받은 K값보다 작은 ..

  • format_list_bulleted 알고리즘 문제 풀이
  • · 2022. 3. 5.
  • textsms
[파이썬] 백준 3053 : 택시 기하학

[파이썬] 백준 3053 : 택시 기하학

[파이썬] 백준 3053 : 택시 기하학 https://www.acmicpc.net/problem/3053 3053번: 택시 기하학 첫째 줄에는 유클리드 기하학에서 반지름이 R인 원의 넓이를, 둘째 줄에는 택시 기하학에서 반지름이 R인 원의 넓이를 출력한다. 정답과의 오차는 0.0001까지 허용한다. www.acmicpc.net 브론즈 3 수학, 기하학 접근 개념 이해를 위해 나무위키를 참조했다. https://namu.wiki/w/%ED%83%9D%EC%8B%9C%20%EA%B8%B0%ED%95%98%ED%95%99 격자 좌표계에서 파란 점이 중심이라 할때, 중심을 기준으로 거리가 2인 지점을 빨간 점으로 표시하면 왼쪽 그림과 같다. 일반적으로 중심을 기준으로 같은 거리를 표시하면 통상적인 원의 형태를..

  • format_list_bulleted 알고리즘 문제 풀이
  • · 2022. 3. 5.
  • textsms