[Python] 백준/BOJ 17291번: 새끼치기 (Silver 2)
·
Algorithm/백준 (BOJ)
💻 Problem문제 보러 가기 실험실에서 새로운 종의 벌레 한 마리가 탄생하였다. 벌레는 스스로 분열하며, 분열하면 자기 자신과 같은 벌레를 한 마리 만들어 내게 된다. 벌레가 분열하는 규칙은 다음과 같다.벌레는 기준연도 1년 2월에 1마리가 탄생한다.벌레는 매년 1월이 되면 분열한다. 분열 시 본래의 개체는 그대로, 새로운 개체가 하나 탄생하는 것으로 본다.홀수 연도에 탄생한 개체는 3번 분열 시, 짝수 연도에 탄생한 개체는 4번 분열 시 사망한다.예를 들어, 기준년도 1년 2월에 존재하던 벌레는, 2년 1월, 3년 1월, 4년 1월에 분열하고 사망하여 4년 말에는 존재하지 않게 된다. 이때, N 년 말에 존재하는 벌레의 수를 구하여라. 💡 Approach먼가.. 문제를 읽어 보니 DP겠다 싶어서..
[Python] 백준/BOJ 21760번: 야구 시즌 (Silver 5)
·
Algorithm/백준 (BOJ)
💻 Problem문제 보러 가기 KOI 야구 리그에는 N개의 지역리그가 존재하고 각 지역리그에는 M개의 팀이 존재해서, 리그 전체로는 N × M개의 팀으로 운영되고 있다.한 시즌에 각 팀은 같은 지역리그 팀뿐만 아니라 다른 지역리그 팀과도 경기를 해야 한다. 같은 지역리그 팀과의 팀당 경기 수는 A로 같은 지역리그 팀들에 대해서 모두 동일하다. 즉, 한 팀 X는 같은 지역리그에 있는 모든 팀 Y (≠ X)와 각각 A번의 경기를 한다. 또한 다른 지역리그 팀과의 팀당 경기 수는 B로 다른 지역리그 팀들에 대해서 모두 동일하다. 즉, 한 팀 X는 다른 지역리그에 있는 모든 팀 Z( ≠ X)와 각각 B번의 경기를 한다. 단, A와 B는 A = k × B (k는 1 이상의 정수)를 만족해야 한다.세계적 판데..
[Python] 백준/BOJ 1932번: 정수 삼각형 (Silver 1)
·
Algorithm/백준 (BOJ)
💻 Problem문제 보러 가기 7 3 8 8 1 0 2 7 4 44 5 2 6 5위 그림은 크기가 5인 정수 삼각형의 한 모습이다.맨 위층 7부터 시작해서 아래에 있는 수 중 하나를 선택하여 아래층으로 내려올 때, 이제까지 선택된 수의 합이 최대가 되는 경로를 구하는 프로그램을 작성하라. 아래층에 있는 수는 현재 층에서 선택된 수의 대각선 왼쪽 또는 대각선 오른쪽에 있는 것 중에서만 선택할 수 있다.삼각형의 크기는 1 이상 500 이하이다. 삼각형을 이루고 있는 각 수는 모두 정수이며, 범위는 0 이상 9999 이하이다. ✏️ Solution 1import sysinput = sys.stdin.readlinen = int(input(..
[Python] 백준/BOJ 14500번: 테트로미노 (Gold 4)
·
Algorithm/백준 (BOJ)
💻 Problem문제 보러 가기 폴리오미노란 크기가 1×1인 정사각형을 여러 개 이어서 붙인 도형이며, 다음과 같은 조건을 만족해야 한다.정사각형은 서로 겹치면 안 된다.도형은 모두 연결되어 있어야 한다.정사각형의 변끼리 연결되어 있어야 한다. 즉, 꼭짓점과 꼭짓점만 맞닿아 있으면 안 된다.정사각형 4개를 이어 붙인 폴리오미노는 테트로미노라고 하며, 다음과 같은 5가지가 있다.아름이는 크기가 N×M인 종이 위에 테트로미노 하나를 놓으려고 한다. 종이는 1×1 크기의 칸으로 나누어져 있으며, 각각의 칸에는 정수가 하나 쓰여 있다.테트로미노 하나를 적절히 놓아서 테트로미노가 놓인 칸에 쓰여 있는 수들의 합을 최대로 하는 프로그램을 작성하시오.테트로미노는 반드시 한 정사각형이 정확히 하나의 칸을 포함하도록 ..
[Python] 백준/BOJ 14626번: ISBN (Bronze 1)
·
Algorithm/백준 (BOJ)
💻 Problem문제 보러 가기 ISBN(International Standard Book Number)은 전 세계 모든 도서에 부여된 고유번호로, 국제 표준 도서번호이다. ISBN에는 국가명, 발행자 등의 정보가 담겨 있으며 13자리의 숫자로 표시된다. 그중 마지막 숫자는 체크기호로 ISBN의 정확성 여부를 점검할 수 있는 숫자이다. 이 체크기호는 일련번호의 앞에서부터 각 자리마다 가중치 1, 3, 1, 3…. 를 곱한 것을 모두 더하고, 그 값을 10으로 나눈 나머지가 0이 되도록 만드는 숫자 m을 사용한다. 수학적으로는 다음과 같다.ISBN이 abcdefghijklm 일 때, a+3b+c+3d+e+3f+g+3h+i+3j+k+3l+m ≡ 0 (mod 10)즉, 체크기호 m = 10 - (a+3b+c..
백준/BOJ: N과 M 문제 모음 (순열/조합 정리)
·
Algorithm/백준 (BOJ)
✏️ 순열과 조합순열: N개 중 중복 없이 M개를 뽑아 순서 있게 나열한다조합: N개 중 중복 없이 M개를 뽑아 순서 없이 나열한다중복순열: N개 중 중복 허용하여 M개를 뽑아 순서 있게 나열한다중복조합: N개 중 중복 허용하여 M개를 뽑아 순서 없이 나열한다 이름중복 허용순서공식itertools순열XOP(N, M) = N! / (N-M)!permutations(iter, M)조합XXC(N, M) = N! / M!(N-M)!combinations(iter, M)중복순열OON^Mproduct(iter, repeat=M)중복조합OXC(N+M-1, M)combinations_with_replacement(iter, M) ✏️ [백준] N과 M 문제 모음 문제를 클릭하면 백준 문제 링크로 이동하고, 풀이를 클..
[Python] 백준/BOJ 15666번: N과 M (12) (Silver 2)
·
Algorithm/백준 (BOJ)
💻 Problem문제 보러 가기 N개의 자연수와 자연수 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오.N개의 자연수 중에서 M개를 고른 수열같은 수를 여러 번 골라도 된다.고른 수열은 비내림차순이어야 한다.길이가 K인 수열 A가 A1 ≤ A2 ≤ ... ≤ AK-1 ≤ AK를 만족하면, 비내림차순이라고 한다. 💡 Approach중복 조 코드를 기반으로 해서 이전값(prev)을 기록하는 변수를 추가했다.이전 값을 기록해서 이전값과 같은 숫자를 또 선택하지 못하게 막았다. 예를 들어, N=4, M=2, num=[1, 2, 3, 3]인 상황을 살펴보자.(1, 1)를 뽑은 후에 두 번째 자리의 숫자를 교체하려고 할 것이다.교체하게 되면 (1, 2)가 되고, 한..
[Python] 백준/BOJ 15665번: N과 M (11) (Silver 2)
·
Algorithm/백준 (BOJ)
💻 Problem문제 보러 가기 N개의 자연수와 자연수 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오.N개의 자연수 중에서 M개를 고른 수열같은 수를 여러 번 골라도 된다. 💡 Approach중복 순열 코드를 기반으로 해서 이전값(prev)을 기록하는 변수를 추가했다.이전 값을 기록해서 이전값과 같은 숫자를 또 선택하지 못하게 막았다. 예를 들어, N=4, M=2, num=[1, 2, 3, 3]인 상황을 살펴보자.(1, 1)를 뽑은 후에 두 번째 자리의 숫자를 교체하려고 할 것이다.교체하게 되면 (1, 2)가 되고, 한 번 더 교체하면 (1, 3)이 된다. 원소가 4개이므로 한 번 더 교체하려고 할 텐데, 여기서 prev가 없다면 3(index 2)에서..