본문 바로가기

BOJ89

백준 알고리즘 2798 (블랙잭) - python [문제] 백준 알고리즘 2798 (블랙잭) > https://www.acmicpc.net/problem/2798 2798번: 블랙잭 문제 카지노에서 제일 인기 있는 게임 블랙잭의 규칙은 상당히 쉽다. 카드의 합이 21을 넘지 않는 한도 내에서, 카드의 합을 최대한 크게 만드는 게임이다. 블랙잭은 카지노마다 다양한 규정이 있다. 한국 최고의 블랙잭 고수 김정인은 새로운 블랙잭 규칙을 만들어 상근, 창영이와 게임하려고 한다. 김정인 버젼의 블랙잭에서 각 카드에는 양의 정수가 쓰여 있다. 그 다음, 딜러는 N장의 카드를 모두 숫자가 보이도록 바닥에 놓는다. 그런 후에 딜러는 숫자 M을 크게 www.acmicpc.net N개의 수가 주어진 배열에서 3개를 선택해 M에 가까운 수를 만드는 문제이다. 주의할 점은 .. 2019. 10. 16.
백준 알고리즘 4948 (베르트랑 공준) - python [문제] 백준 알고리즘 4948 (베르트랑 공준) > https://www.acmicpc.net/problem/4948 4948번: 베르트랑 공준 문제 베르트랑 공준은 임의의 자연수 n에 대하여, n보다 크고, 2n보다 작거나 같은 소수는 적어도 하나 존재한다는 내용을 담고 있다. 이 명제는 조제프 베르트랑이 1845년에 추측했고, 파프누티 체비쇼프가 1850년에 증명했다. 예를 들어, 10보다 크고, 20보다 작거나 같은 소수는 4개가 있다. (11, 13, 17, 19) 또, 14보다 크고, 28보다 작거나 같은 소수는 3개가 있다. (17,19, 23) n이 주어졌을 때, n보다 크고, 2n보 www.acmicpc.net 임의의 자연수 n에 대해 n < x 2019. 10. 16.
백준 알고리즘 1929 (소수 구하기) - python [문제] 백준 알고리즘 1929 (소수 구하기) > https://www.acmicpc.net/problem/1929 1929번: 소수 구하기 첫째 줄에 자연수 M과 N이 빈 칸을 사이에 두고 주어진다. (1 ≤ M ≤ N ≤ 1,000,000) www.acmicpc.net 에라토스테네스의 체를 이용하라는 문제이다. 소수를 구하기 위해 합성수를 제거하는 방식으로, 2부터 N까지 배수를 제거한다. 2부터 N까지의 소수를 구하기 위해선, N의 제곱근까지만 검사하면 된다. range(N)이 N-1까지이고, 배열이 0부터 시작하는 특성상, 받아온 N을 +1 해주는 트릭을 썼다. [Code] M, N = map(int, input().split()) def prime_sieve(M, N): N += 1 sieve.. 2019. 10. 16.
백준 알고리즘 13460 (구슬 탈출 1,2) - python [문제] 백준 알고리즘 13459 (구슬 탈출) > https://www.acmicpc.net/problem/13459 13459번: 구슬 탈출 첫 번째 줄에는 보드의 세로, 가로 크기를 의미하는 두 정수 N, M (3 ≤ N, M ≤ 10)이 주어진다. 다음 N개의 줄에 보드의 모양을 나타내는 길이 M의 문자열이 주어진다. 이 문자열은 '.', '#', 'O', 'R', 'B' 로 이루어져 있다. '.'은 빈 칸을 의미하고, '#'은 공이 이동할 수 없는 장애물 또는 벽을 의미하며, 'O'는 구멍의 위치를 의미한다. 'R'은 빨간 구슬의 위치, 'B'는 파란 구슬의 위치이다. 입력되는 모든 보드 www.acmicpc.net [문제] 백준 알고리즘 13460 (구슬 탈출 2) > https://www.a.. 2019. 10. 16.
백준 알고리즘 1759 (암호 만들기) - python [문제] 백준 알고리즘 1759 (암호 만들기) > https://www.acmicpc.net/problem/1759 1759번: 암호 만들기 첫째 줄에 두 정수 L, C가 주어진다. (3 ≤ L ≤ C ≤ 15) 다음 줄에는 C개의 문자들이 공백으로 구분되어 주어진다. 주어지는 문자들은 알파벳 소문자이며, 중복되는 것은 없다. www.acmicpc.net N과 M의 연장선에 있는 문제이다. C와 L로 이름만 바뀌었다. 조건은 최소 1개의 모음과 2개의 자음으로 구성된 암호이고, 사전식으로 가능성 있는 암호를 모두 출력하는 문제이다. 1. 먼저 얻은 배열을 sort() 한다. (문자열 순으로도 됨) L자리의 암호 얻기 위해서 DFS를 적용, 이 때 idx를 i+1을 넘겨주어 사전식으로 가능한 것들만 출력.. 2019. 10. 16.
백준 알고리즘 15665 (N과 M(11)) - python [문제] 백준 알고리즘 15665 (N과 M(11)) - python > https://www.acmicpc.net/problem/15665 15665번: N과 M (11) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해야 한다. www.acmicpc.net N과 M(10)에서 비내림차순 조건을 제외하고, 같은 수를 출력해도 되는 문제 1. 비내림차순 조건을 위해 사용했던 idx로 range 조절 방법을 뺀다. 2. 같은 수를 여러 번 골라도 되므로 visited 방법을 뺀다. [Code] N, M = map(int, input().split()) L = list(m.. 2019. 10. 16.
백준 알고리즘 2581 (소수) - python [문제] 백준 알고리즘 2581 (소수) - python > https://www.acmicpc.net/problem/2581 2581번: 소수 M이상 N이하의 자연수 중 소수인 것을 모두 찾아 첫째 줄에 그 합을, 둘째 줄에 그 중 최솟값을 출력한다. 단, M이상 N이하의 자연수 중 소수가 없을 경우는 첫째 줄에 -1을 출력한다. www.acmicpc.net 1978번(소수 찾기)이랑 비슷한 문제이다. 다른 점은 배열이 주어지는 것이 아니라 범위가 주어지고, 소수들의 합을 출력하거나 소수가 범위안에 없을 때는 -1을 출력하는 정도이다. 1978번 풀었을 때와 풀이 방법은 거의 같다. 1이 아닌 요소(i)를 하나씩 꺼내면서 2~ i-1까지 나눠지는 수가 없을 때만을 골라낸다. 나눠지는 수가 존재하면 더 .. 2019. 10. 16.
백준 알고리즘 15664 (N과 M(10)) - python [문제] 백준 알고리즘 15664 (N과 M(10)) - python > https://www.acmicpc.net/problem/15664 15664번: N과 M (10) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해야 한다. www.acmicpc.net N과 M(9)에서 비내림차순 조건이 붙은 문제. N과 M(9)와 같은 방법에서 idx로 i+1을 넘겨주어 range를 조정해주면 해결. [Code] N, M = map(int, input().split()) L = list(map(int, input().split())) L.sort() visited = [Fal.. 2019. 10. 16.
백준 알고리즘 15663 (N과 M(9)) - python [문제] 백준 알고리즘 15663 (N과 M(9)) - python > https://www.acmicpc.net/problem/15663 15663번: N과 M (9) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해야 한다. www.acmicpc.net 이제는 N개의 자연수 중에 겹치는 수가 존재할 수 있는 문제다. 결론부터 말하면 처음에는 시간초과로 계속 실패했다. (pypy3로는 간신히 통과) 접근법 자체가 문제는 아니었고, 원인은 python에서 편리하게 쓰는 'if A in B' 이다. 이 구문이 A가 B배열 안에 소속되어 있는지를 검사하기 위해 for문이나.. 2019. 10. 16.
728x90

티스토리툴바