본문 바로가기

백준 파이썬 코딩

 (49)
백준 1780 종이의 개수 파이썬 https://www.acmicpc.net/problem/1780 1780번: 종이의 개수 N×N크기의 행렬로 표현되는 종이가 있다. 종이의 각 칸에는 -1, 0, 1 중 하나가 저장되어 있다. 우리는 이 행렬을 다음과 같은 규칙에 따라 적절한 크기로 자르려고 한다. 만약 종이가 모두 같은 수 www.acmicpc.net 종이를 9개의 부분으로 나눈뒤 탐색을 해주면 되는 간단한 문제였다. *한가지 주의할 점은 pypy로 제출해야 했고, 나누기전 초기 종이에서도 한번 탐색을 해줘야 하는 것이다. (처음부터 성분이 1개일때.) def ch(s,a,b,c,d):#9개의 부분중 한 부분을 탐색하는 함수이다. global re ch = set() t = 0 e=[] for i in range(a,b): e.app..
백준 17822 원판 돌리기 파이썬 https://www.acmicpc.net/problem/17822 17822번: 원판 돌리기 반지름이 1, 2, ..., N인 원판이 크기가 작아지는 순으로 바닥에 놓여있고, 원판의 중심은 모두 같다. 원판의 반지름이 i이면, 그 원판을 i번째 원판이라고 한다. 각각의 원판에는 M개의 정수가 적혀 www.acmicpc.net *중요한 포인트* 1. 바로 deque를 떠올리는 것 (방향에따라 appendleft(pop()) // append(popleft()))해주기 위해 2. x 배수의 원판만 돌아간다는 것. 3. 숫자 삭제와 증감은 모든 원판이 다 돌아가고 일어난다는 것 (제일 중요) 4. 원판 안의 모든 숫자가 0일 수 있다.(런타입 에러 관련) 코드 설명은 코드 주석으로 하겠습니다. from co..
백준 14246 K보다 큰 구간 파이썬 반례 1개 O https://www.acmicpc.net/problem/14246 14246번: K보다 큰 구간 n개의 자연수로 이루어진 수열이 주어질 때, 특정 구간 [i,j](i≤j)의 합이 k보다 큰 모든 쌍 i,j의 개수를 출력하시오. www.acmicpc.net 처음에는 시간 복잡도를 생각하지 않고 한번 작성해봤다. O(N^2) (결과는 당연히 시간 초과.) n = int(input()) s = list(map(int,input().split())) k = int(input()) sums = 0 re =0 for i in range(n): sums = s[i] for j in range(i+1,n): sums+=s[j] if sums>k: re+=(n-j) break print(re) 위에 코드에서도 알 수 ..
백준 16236 아기상어 파이썬 https://www.acmicpc.net/problem/16236 16236번: 아기 상어 N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 물고기가 최대 1마리 존재한다. 아기 상어와 물고기는 모두 크기를 가 www.acmicpc.net 간단한 BFS문제에 우선순위가 추가된 문제였다. from collections import deque import heapq def bfs(q): global re vist = [[False]*n for _ in range(n)]#방문체크 h=[]#우선순위 연산을 해줄 heapq while q: x,y,c,size,up = q.popleft() for k in range(4): nx = x..
백준 17299 오등큰수 파이썬 문제 설명 O heapq사용 https://www.acmicpc.net/problem/17299 17299번: 오등큰수 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째에 수열 A의 원소 A1, A2, ..., AN (1 ≤ Ai ≤ 1,000,000)이 주어진다. www.acmicpc.net 문제 해석부터가 어려웠던 문제였다. 뒤에 해석까지 있었으면 더 이해하기 편했을거 같다. A4가 왜 2가 되냐면 A[4~n] 까지 나온 수를 보면 3, 4, 2, 1이 나왔음을 알 수 있다. (굵은 숫자가 비교 값) 차례대로 1, 1, 2, 3인데 비교 대상은 1이다. 따라서 1보다 큰 수 중에 가장 왼쪽에 있는 값(비교 값 보다 큰 수가 처음 나온 위치의 수 )을 해줘야하는데 그 수가 2번나온 2여서 A4는 ..
백준 12100 2048 파이썬 반례 O https://www.acmicpc.net/problem/12100 12100번: 2048 (Easy) 첫째 줄에 보드의 크기 N (1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에는 게임판의 초기 상태가 주어진다. 0은 빈 칸을 나타내며, 이외의 값은 모두 블록을 나타낸다. 블록에 쓰여 있는 수는 2 www.acmicpc.net *반례는 맨 아래 있다.*(정답이 아닌 움직였을때 어떻게 되야하는지.) 학창시절에 폰으로 즐겨 했던 게임을 구현해보는 문제였다. 문제에서 "최대 5번 이동해서 만들 수 있는 가장 큰 블록의 값을 구하는 프로그램을 작성하시오."라느 말을 처음 봤을때 모든 경우의 수를 돌려보면 될거 같았다. 그래서 0,1,2,3(오른쪽,왼쪽,아래,위)를 임의로 설정해 백트레킹을 해줘 길이..
백준 10971 외판원 순회 2 파이썬 https://www.acmicpc.net/problem/10971 10971번: 외판원 순회 2 첫째 줄에 도시의 수 N이 주어진다. (2 ≤ N ≤ 10) 다음 N개의 줄에는 비용 행렬이 주어진다. 각 행렬의 성분은 1,000,000 이하의 양의 정수이며, 갈 수 없는 경우는 0이 주어진다. W[i][j]는 도시 i에서 j www.acmicpc.net 순열 함수를 알고 있으면 쉬운 문제였다. pypy로 제출하면 AC받을 수 있다. import sys import itertools input = sys.stdin.readline n = int(input()) s = [list(map(int,input().split())) for _ in range(n)]#i->j거리를 나타내주는 map를 만들어줌 t ..
백준 1541 잃어버린 괄호 파이썬 https://www.acmicpc.net/problem/1541 1541번: 잃어버린 괄호 첫째 줄에 식이 주어진다. 식은 ‘0’~‘9’, ‘+’, 그리고 ‘-’만으로 이루어져 있고, 가장 처음과 마지막 문자는 숫자이다. 그리고 연속해서 두 개 이상의 연산자가 나타나지 않고, 5자리보다 www.acmicpc.net -가 나오면 괄호를 쳐주면 되는 간단한 문제였다. 이해가 잘 안 될수 있으므로 주석에 설명을 첨가하겠습니다. #ex) a+b+c-x+y+e-d+w+q s = input().split('-')# -가 나온만큼 빼주면 되므로 -가 나오면 분리해줌. s=[(a+b+c),(x+y+e),(d+w+q)] for i in range(len(s)): s[i] = sum(list(map(int,s[i].sp..

티스토리툴바