알고리즘 (14) 썸네일형 리스트형 [Python] BOJ 백준 21923 곡예 비행 문제 동헌이는 모형 비행기 조종 대회에 참가하였다. 이 대회에서는 격자 모양의 공간에서 모형 비행기를 조종하여 얻는 비행 점수로 순위를 매긴다. 격자의 각 칸에는 점수가 부여되어 있고, 비행 점수는 "상승 비행을 할 때 지나간 칸에 부여된 점수의 총합"과 "하강 비행을 할 때 지나간 칸에 부여된 점수의 총합"을 더한 값이다. 출발한 칸과 도착한 칸도 지나간 칸으로 간주한다. 시작과 끝 칸 및 가능한 이동 방향 모형 비행기는 맨 왼쪽 아래 칸에서 상승 비행으로 비행을 시작해야 하고, 중간에 상승 비행에서 하강 비행으로 변경한 후, 맨 오른쪽 아래 칸에서 하강 비행으로 비행을 종료해야 한다. 상승 비행에서 하강 비행으로 변경할 때에는 다른 칸으로 이동할 수 없다. 즉, 상승 비행이 끝난 칸에서 하강 비행을 .. [Python] BOJ 백준 21922 학부연구생 민상 문제 학부 연구생으로 새로 연구실에 들어온 민상이는 사용할 자리를 정하려고 한다. 연구실은 격자 모양으로 되어있고 에어컨에서 바람이 상,하,좌,우 4방향으로 분다. 물론 에어컨이 위치한 곳에도 바람이 분다. 민상이는 더위를 많이 타서 에어컨 바람이 지나가는 곳 중 하나를 선택하여 앉으려고 한다. 연구실에는 다양한 물건들이 있어 바람의 방향을 바꾼다. 연구실에 있는 물건의 종류는 총 4가지가 있다. 아래 화살표의 의미는 바람이 각 물건에서 바람의 이동을 표시한 것이다. 연구실 어디든 민상이가 앉을 수 있는 자리이다. 즉 에어컨이 위치한 자리와 물건이 있는 자리 모두 앉을 수 있다. 민상이가 원하는 자리는 몇 개 있는지 계산해주자. 풀이 from collections import deque import sy.. [Python] BOJ 백준 21921 블로그 문제 찬솔이는 블로그를 시작한 지 벌써 N일이 지났다. 요즘 바빠서 관리를 못 했다가 방문 기록을 봤더니 벌써 누적 방문 수가 6만을 넘었다. 찬솔이는 X일 동안 가장 많이 들어온 방문자 수와 그 기간들을 알고 싶다. 찬솔이를 대신해서 X일 동안 가장 많이 들어온 방문자 수와 기간이 몇 개 있는지 구해주자. 첫째 줄에 X일 동안 가장 많이 들어온 방문자 수를 출력한다. 만약 최대 방문자 수가 0명이라면 SAD를 출력한다. 만약 최대 방문자 수가 0명이 아닌 경우 둘째 줄에 기간이 몇 개 있는지 출력한다. 풀이 N과 X, 방문자 배열을 입력받아서 연속되는 숫자들의 최대 부분합을 구하는 문제였다. 초기에는 단순하게 index를 sum을 이용해서 구하면서 최대값을 갱신시키는 방향으로 진행했는데, 시간초과가 났.. [Python] BOJ 백준 21920 서로소평균 문제 효성이는 길이가 N인 수열 A에서 X와 서로소인 수들을 골라 평균을 구해보려고 한다. 효성이를 도와 이를 계산해주자. 첫째 줄에 수열 A에서 X와 서로소인 수들의 평균을 출력한다. 절대/상대 오차는 10**6까지 허용한다. 풀이 서로소는 두 수의 최대공약수가 1인 경우를 말한다. 최대공약수를 구하는 함수를 이용해서 쉽게 풀 수 있었다. 최대공약수 혹은 최소공배수를 이용하는 문제들은 자주 등장하기 때문에 외워두는 편이 정신건강에 이로운 것 같다. import sys si = sys.stdin.readline n = int(si()) arr = list(map(int, si().split())) x = int(si()) answer, cnt = 0, 0 def gcd(a, b): while b: a, .. [Python] BOJ 백준 21919번 소수최소공배수 문제 행복이는 길이가 N인 수열 A에서 소수들을 골라 최소공배수를 구해보려고 한다. 행복이를 도와 이를 계산해주자. 첫째 줄에 수열 A의 길이 N이 주어진다. (1≤N≤10,000) 그 다음줄에는 수열 A의 원소 Ai가 공백으로 구분되어 주어진다. (2≤Ai≤1,000,000) 답이 2**63 미만인 입력만 주어진다. 풀이 최대공약수, 최소공배수를 구하는 함수를 이용했다. 소수들의 최소공배수를 구할 때, 소수들은 서로 최대공약수가 1이기 때문에 그냥 전부 곱해주면 된다. from math import sqrt import sys si = sys.stdin.readline n = int(si()) arr = list(map(int, si().split())) prime_list = [] def is_pri.. [Python] BOJ 백준 21918번 전구 문제 N개의 전구가 있고 맨 왼쪽에 있는 전구를 첫 번째라고 하자. 전구의 상태는 두 가지가 있으며 이를 숫자로 표현한다. 1은 전구가 켜져 있는 상태를 의미하고, 0은 전구가 꺼져 있는 상태를 의미한다. 전구를 제어하는 명령어가 1번부터 4번까지 4개가 있다. 아래 표는 각 명령어에 대한 설명이다. 모든 명령어를 수행한 후 전구가 어떤 상태인지 출력한다. 풀이 이 문제는 단순 하드코딩으로 풀 수 있는 문제였다. 들어온 명령에 따라서 비트 연산으로 반전 시키는 법도 존재한다고 한다. import sys si = sys.stdin.readline n, m = map(int, si().split()) arr = list(map(int, si().split())) def command(c): global ar.. 이전 1 2 다음
