4384 공평하게 팀 나누기 (백준, python3)
·
PS/BOJ
시간 제한메모리 제한1초128MB문제학생회장을 하고 있는 상근이는 이번 학교 축제 행사로 학우들간의 친밀감을 돈독히 하고자 줄다리기를 하려 한다. 하지만 이 줄다리기에 형평성을 최대한 고려하기위해 두 팀간의 사람 수 차이를 1 이하로 하려하며, 두 팀간의 몸무게의 차이가 최소화되도록 하고자 한다. 이때 상근이가 나누려 하는 두 팀의 몸무게를 각각 출력 하시오. 입력가장 첫 번째 줄에 줄다리기를 하기 원하는 총 인원의 수(1 ≤ N ≤ 100)가 주어진다. 이후 N개의 줄에 줄다라기에 참여하기 원하는 사람의 몸무게(1 ≤ K ≤ 450)가 주어진다. 출력두팀의 몸무게를 작은 순서대로 순차적으로 출력한다. 풀이N명이 주어졌을 때, 한 팀에 있을 수 있는 최대 인원은 N//2명 또는 N//2+1명이다. 여기서..
3770 대한민국 (백준, python3)
·
PS/BOJ
시간 제한메모리 제한1초128MB문제대한민국은 동아시아에 위치한 한반도에 위치하고 있다. 3면이 바다인 한국의 서쪽으로 서해, 동쪽으로 동해, 남쪽으로 남해에 의해 둘러싸여 있다. 대한민국의 동해안에는 도시가 N개 있고, 서해안에는 도시가 M개 있다. (M ≤ 1000, N ≤ 1000) 각 도시는 북쪽부터 남쪽까지 번호가 1번부터 매겨져 있다. 새로 취임한 대통령은 서해안과 동해안을 연결하는 K개의 고속도로를 만들려고 한다. 각 고속도로는 동해안에 있는 도시와 서해안에 있는 도시를 연결하는 일직선 도로이다. (원래 일직선인 도로는 운전사를 지루하게 하고 피로감을 느끼게 하여 사고의 원인이 되므로, 일부러 고저를 만들거나 커브를 만들어서 그러한 일이 일어나지 않도록 설계되어 있다) 고속도로가 서로 교차하..
0과 1, False와 True에서의 비트연산자
·
python
파이썬의 Boolean타입 파이썬에서는 True를 대체할 수 있는 다양한 수단이 존재한다. 예를 들어 이런 것들 numbers = map(int, input().split()) count = 0 while numbers: numbers.pop() count += 1 print(count) numbers 배열의 길이가 0이 아니라면 while에 True로 전달된다. 또는 이런 것 k = 0 k = int(input()) if k: print("k has been changed") else: print("k is still zero") k의 값이 0이라면 if문에서 False로, 0이 아니라면 True로 전달된다. (정확히는 아님) 따라서 이런 표면적인 현상에 익숙해지면 이런 끔찍한 실수를 저지를 수 있는데..
최단거리를 찾는 세 가지 방법(Shortest path problem)
·
PS/Algorithm
1. 다익스트라 알고리즘(Dijksrta)시작 정점으로부터 간선으로 연결된 정점들을 순차적으로 방문한다. 간선의 가중치를 포함해 방문한 정점의 거리가 갱신된다면 방문한 정점에서 이 과정을 다시 반복한다. 원리만 따지면 너비우선탐색과 크게 다르지 않다. 모든 간선의 가중치가 1인 그래프가 주어진다면 너비우선탐색을 실시하는 것이 다익스트라와 같은 효과가 있다.이런 무향 그래프가 있다고 할 때 1에서부터 6까지의 최단거리를 구해보자. 먼저 모든 정점의 거리를 충분히 큰 값인 inf로 설정한다. 실제로 무한일 필요는 없고 탐색하고자 하는 모든 상황에 대해 예상되는 최대 탐색 거리보다 크기만 하면 된다. 최대 정점의 수가 V개이고 간선의 최대 가중치가 W라면 inf는 V*W보다 큰 값이면 된다. 탐색의 출발 정점..
15684 사다리 조작 (백준, python3)
·
PS/BOJ
시간 제한메모리 제한2초512MB문제(그림생략)사다리 게임은 N개의 세로선과 M개의 가로선으로 이루어져 있다. 인접한 세로선 사이에는 가로선을 놓을 수 있는데, 각각의 세로선마다 가로선을 놓을 수 있는 위치의 개수는 H이고, 모든 세로선이 같은 위치를 갖는다. 아래 그림은 N = 5, H = 6 인 경우의 그림이고, 가로선은 없다.초록선은 세로선을 나타내고, 초록선과 점선이 교차하는 점은 가로선을 놓을 수 있는 점이다. 가로선은 인접한 두 세로선을 연결해야 한다. 단, 두 가로선이 연속하거나 서로 접하면 안 된다. 또, 가로선은 점선 위에 있어야 한다.위의 그림에는 가로선이 총 5개 있다. 가로선은 위의 그림과 같이 인접한 두 세로선을 연결해야 하고, 가로선을 놓을 수 있는 위치를 연결해야 한다. 사다리..
12899 데이터 구조 (백준, python3)
·
PS/BOJ
시간 제한메모리 제한2초512MB문제자연수를 저장하는 데이터베이스 S에 대해 다음의 쿼리를 처리합시다. 유형 1 : S에 자연수 X를 추가한다. 유형 2 : S에 포함된 숫자 중 X번째로 작은 수를 응답하고 그 수를 삭제한다. 입력첫째 줄에 사전에 있는 쿼리의 수 N 이 주어집니다. (1 ≤ N ≤ 2,000,000) 둘째 줄부터 N개의 줄에 걸쳐 각 쿼리를 나타내는 2개의 정수 T X가 주어집니다. T가 1이라면 S에 추가할 X가 주어지는 것입니다. (1 ≤ X ≤ 2,000,000) T가 2라면 X는 S에서 삭제해야 할 몇 번째로 작은 수인지를 나타냅니다. S에 최소 X개의 원소가 있음이 보장됩니다. 출력유형 2의 쿼리 개수만큼의 줄에 각 쿼리에 대한 답을 출력합니다. 풀이S를 어떤 자료 구조로 관리..
2024 가지컵 참가 후기
·
PS/BOJ
A 가지 한 두름 주세요 간단한 배열 탐색 문제. 10*10 크기의 작은 배열이기 때문에 그냥 브루트포스 돌려서 모든 행과 열을 탐색해 똑같은 문자로만 이루어진 행, 열이 존재하면 1, 아니면 0을 출력한다. D :rightplant: 정말 심각하게 시간 오래 끌어서 패널티 폭탄 맞은 문제. 양쪽으로 배열 관리를 하며 다음 수를 왼쪽에 넘겨줄지, 오른쪽에 넘겨줄지 결정한다. 결정 기준은 새로 추가될 숫자를 포함 왼쪽과 오른쪽의 차이가 가장 적게 나는 쪽으로 넘겨주면 된다. [left - 1 - right]와 같은 식으로 배열을 관리하면 되는데, 만약 left 총합 + 1보다 right 총합이 크거나 같다면 left의 모든 숫자들을 1씩 증가시키고 1을 left에 append. 아닌 경우는 반대로 righ..
31567 Move or Block! (백준, python3)
·
PS/BOJ
시간 제한메모리 제한1초1024MB문제「Move or Block!」 게임은 N칸의 일자형 게임보드에서 할 수 있는 2인용 보드게임이다. 게임보드의 각 칸은 비어 있거나 벽이 세워져 있으며, 비어 있는 칸 중 하나에 두 플레이어가 움직일 수 있는 하나의 말을 올려두고 게임을 시작한다. 게임은 두 명의 플레이어가 턴을 번갈아 가면서 진행한다. 각 플레이어는 자신의 턴이 되었을 때 말의 인접한 칸에 모두 벽이 세워져 있으면 패배한다. 아니라면 아래 두 가지 행동 중 하나를 선택하여 한 번 플레이하고 턴을 넘긴다.말을 비어 있는 인접한 칸 중 하나로 움직인다.비어 있는 칸을 하나 골라 벽을 세운다.민규와 윤수가 「Move or Block!」 게임을 하려 한다. 주어진 게임보드에서 두 플레이어 모두 최적의 방법으..
12911 좋아하는 배열 (백준, python3)
·
PS/BOJ
시간 제한메모리 제한2초512MB문제성관이는 다음과 같은 성질을 만족하는 배열을 좋아한다. 배열의 길이는 N이다.배열에 채워져있는 수는 1보다 크거나 같고, K보다 작거나 같은 자연수이다.배열에서 연속한 수가 A와 B일 때, A 예를 들어, N = 4, K = 7인 경우에 [1, 7, 7, 2]는 성관이가 좋아하는 배열이다. 모든 연속한 수가 1 N과 K가 주어졌을 때, 성관이가 좋아하는 배열의 경우의 수를 구하는 프로그램을 작성하시오.입력첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 10, 1 ≤ K ≤ 100,000) 출력첫째 줄에 성관이가 좋아하는 배열의 개수를 1,000,000,007로 나눈 나머지를 출력한다. 풀이성관이가 좋아하는 배열의 세 번째 조건을 그대로 사용하지 않고 부정을 취하는 것이..
24229 모두싸인 출근길 (백준, python3)
·
PS/BOJ
시간 제한메모리 제한1초512MB문제취준생 주헌이는 드디어 취업에 성공했다. 주헌이가 취직한 회사는 비대면 전자계약 서비스 모두싸인(MODUSIGN) 이라는 회사이다. 그리고 오늘은 첫 출근날이다. 주헌이의 출근길에는 다리가 있는데, 전날에 비가 많이 오는 바람에 다리가 끊어져 판자 여러 개로 쪼개져 버렸다. 주헌이는 무사히 회사에 도착할 수 있을까? 다리는 수직선으로 나타낼 수 있으며, 각 판자는 구간 [ L, R ]의 범위에 놓여 있다. 주헌이는 0에서 출발하여 오른쪽(양의 방향)으로만 이동한다. 판자로 덮인 좌표는 자유롭게 건너갈 수 있다. 하지만 판자로 덮이지 않은 좌표는 오직 주헌이가 점프를 해야만 건너갈 수 있으며, 점프를 할 경우 착지한 위치에 판자가 놓여 있어야 한다. 판자의 양 끝점에도 ..
20149 선분 교차 3 (백준, python3)
·
PS/BOJ
시간 제한메모리 제한0.25초512MB문제2차원 좌표 평면 위의 두 선분 L1, L2가 주어졌을 때, 두 선분이 교차하는지 아닌지 구해보자. 한 선분의 끝 점이 다른 선분이나 끝 점 위에 있는 것도 교차하는 것이다. L1의 양 끝 점은 (x1, y1), (x2, y2), L2의 양 끝 점은 (x3, y3), (x4, y4)이다. 입력첫째 줄에 L1의 양 끝 점 x1, y1, x2, y2가, 둘째 줄에 L2의 양 끝 점 x3, y3, x4, y4가 주어진다. 출력L1과 L2가 교차하면 첫째 줄에 1, 아니면 0을 출력한다. 두 선분이 한 점에서 교차하는 경우 둘째 줄에 교차하는 점의 x좌표와 y좌표를 공백으로 구분해 출력한다. 한 점에서 교차하지 않는 경우에는 둘째 줄을 출력하지 않는다. 좌표의 절대/상대..
31434 당근 클릭 게임 (백준, python3)
·
PS/BOJ
시간 제한메모리 제한2초1024MB문제에릭은 방학 동안 너무 심심한 나머지, 당근 클릭 게임이라는 게임을 직접 만들어서 플레이하기로 했다. 이 게임에서 초기에 에릭은 당근을 0개 가지고 있고, s가 1인 상태로 게임을 시작한다.그 후, 매초 다음 두 가지의 행동 중 하나를 할 수 있다.마우스를 클릭하고 당근을 s개 얻는다.정수 i (1 ≤ i ≤ N)를 고르고, 당근 Ai개를 지불하여 i번째 스피드 효과를 구매한다. 구매 직후, s가 Bi만큼 증가한다. (이전에 구매한 스피드 효과를 다시 구매하는 것도 가능하다.)게임을 개발하느라 에너지를 모두 소모해 버린 에릭을 위해 게임을 K초 플레이한 후 당근을 최대 몇 개까지 가지고 있을 수 있는지 알려주자!입력첫 번째 줄에 두 정수 N, K가 공백으로 구분되어 ..
전라남도교육지원청
맞았습니다!!
상단으로

티스토리툴바