본문 바로가기

분류 전체보기

 (113)
[BOJ] 제1회 천하제일 코딩대회 예선 풀이 A번 와이버스 부릉부릉 문제 링크: https://www.acmicpc.net/problem/14645 14645번: 와이버스 부릉부릉 첫 줄에 출발역과 종착역을 제외한 정거장의 수 N(1 ≤ N ≤ 100,000)과 출발역에서 탑승하는 사람의 수 K(1 ≤ K ≤ 10,000)가 주어진다. 둘째 줄부터 N개의 줄에 걸쳐 각 줄마다 i번째 정거장에서 탑승 www.acmicpc.net 문제 풀이 구현 문제에 버스 운전수 '비와이' 씨라고 적혀있으므로 비와이를 출력하면 된다. 코드 B번 욱제는 결정장애야!! 문제 링크: https://www.acmicpc.net/problem/14646 14646번: 욱제는 결정장애야!! 욱제는 매일 세계사에 한 획을 그을만한 심각한 비결정론적 문제에 직면한다. 그렇다. 바..
[BOJ][Python] 백준 9370번 - 미확인 도착지 문제 링크: https://www.acmicpc.net/problem/9370 9370번: 미확인 도착지(취익)B100 요원, 요란한 옷차림을 한 서커스 예술가 한 쌍이 한 도시의 거리들을 이동하고 있다. 너의 임무는 그들이 어디로 가고 있는지 알아내는 것이다. 우리가 알아낸 것은 그들이 s지점에서www.acmicpc.net문제 풀이데이크스트라 처음에는 g와 h를 방문 했는지에 따라 처리를 했었다. g-h혹은 h-g를 방문했다고 체크를 하면서 해당 번호에 저장을 했었다. 문제는 가중치가 같은데 하나는 g-h 간선을 방문했고 하나는 방문을 안했다면 덮어질 수도 있다. 이 점까지 체크했고 정답을 확신 했었다. 하지만 이제는 시간 초과가 나기 시작했다. 아무래도 가중치가 같은 값이 수없이 많으면 또 그만큼 돌..
[BOJ][Python] 백준 9011번 - 순서 문제 링크: https://www.acmicpc.net/problem/9011 9011번: 순서 n개의 정수로 된 순서 S= (s1, s2, ..., sn)가 있다. 여기서 si ≠ sj이고, 1 ≤ si ≤ n이다. S로부터 새로운 순서 R = (r1, r2, ..., rn)을 얻을 수 있는데, 여기서 ri는 S의 부분 순서 {s1, s2, ..., si-2, si-1} 중에서 www.acmicpc.net 문제 풀이 구현 R 수열의 뒷부분부터 처리하면 어렵지 않다. 처리는 R[i]+1을 중심으로 하면 된다. 가령 R수열의 마지막은 오른쪽 부분이 없고 왼쪽에는 자신보다 작은 수의 개수이므로 R[i]+1로 자명하다. 그렇다면 중복 혹은 자신보다 작은 수가 오른쪽에 있는 경우는 어떻게 해야할까? 예제 1을 ..
[BOJ][Python] 백준 16973번 - 직사각형 탈출 문제 링크: https://www.acmicpc.net/problem/16973 16973번: 직사각형 탈출 크기가 N×M인 격자판에 크기가 H×W인 직사각형이 놓여 있다. 격자판은 크기가 1×1인 칸으로 나누어져 있다. 격자판의 가장 왼쪽 위 칸은 (1, 1), 가장 오른쪽 아래 칸은 (N, M)이다. 직사각형의 가장 www.acmicpc.net 문제 풀이 너비 우선 탐색, 누적 합 BFS를 이용하는 건 그다지 어렵지 않다. 대부분의 BFS 문제처럼 직사각형의 왼쪽 가장자리를 기준으로 방문하지 않았다면 방문해주고 벽이라면 방문하지 않는 등 일반적인 문제랑 비슷하다. 하지만 직사각형 전체 중에 벽이 있다는 걸 확인하는건 어떻게 해야할까? 먼저 H*W번을 매번 방문할 때 마다 체크해준다? 딱봐도 시간 초과..
[BOJ][Python] 백준 4658번 - 삼각형 게임 문제 링크: https://www.acmicpc.net/problem/4658 4658번: 삼각형 게임 삼각형 게임은 시작할때 여섯개의삼각형을 부여받는데, 각 변에는 숫자가 쓰여있다(그림 참고). 이 삼각형들을 돌리고 움직여서 육각형을 만들어야 하는데, 반드시같은 숫자가 쓰여있는 변끼리 www.acmicpc.net 문제 풀이 브루트포스 알고리즘 브루트포스로 대충 돌려서 풀었다. 테케가 몇 개인지 모르지만 한번 할때 $6!*3^{6}$ 정도니 시간 안에 들거 같다. 일단 삼각형을 입력받고 왼쪽 숫자는 0, 오른쪽 숫자는 1, 밑변 숫자는 2로 인덱스를 정하자. 다음 그림과 같다. 이런 삼각형이 주어졌을 때, 순서가 정해져있지 않기 때문에 순열을 이용해주고, i번의 삼각형의 1번 인덱스와 i+1번의 삼각형의..
[BOJ][Python] 백준 4696번 - St. Ives 문제 링크: https://www.acmicpc.net/problem/4696 4696번: St. Ives Input consists of multiple data sets. Each data set consists of a line with a single floating point number number representing the numbers of wives, sacks per wife, cats per sack, and kittens per cat that Robert encountered that year. End of input is indic www.acmicpc.net 문제 풀이 사칙연산 $1+n+n^{2}+n^{3}+n^{4}$ 를 구한 후 소숫점 셋째 자리에서 반올림 한다. 코드
[BOJ][Python] 백준 11434번 - Ampelmännchen 문제 링크: https://www.acmicpc.net/problem/11434 11434번: Ampelmännchen When you unite two countries, they will typically have their own versions of most things, like road signs, foods, etc. If you basically have one of the countries “impose” its version on the other, this may feel to the other more like an annexation than www.acmicpc.net 문제 풀이 사칙연산 서쪽 사람들이 본인의 비전을 좋아하는 값과 동쪽 사람들이 서쪽 비전을 좋아하는 값을 더한 값..
[BOJ][Python] 백준 2344번 - 거울 문제 링크: https://www.acmicpc.net/problem/2344 2344번: 거울 세로 N, 가로 M 크기의 상자가 있다. 이 상자 안에는 몇 개의 거울이 들어 있다. 상자를 위에서 봤을 때, 거울은 한 칸 안에 대각선 모양으로 들어있다고 한다. 또, 상자의 테두리를 따라서 칸마다 www.acmicpc.net 문제 풀이 시뮬레이션 전형적인 시뮬레이션 문제이다. 5 4 0 1 0 0 0 0 1 0 0 0 1 0 0 0 0 1 0 1 0 0 으로 주어졌을 때를 시뮬레이션 해보자. 1~5번의 경우는 다음과 같다. 좌표와 방향을 이용해서 적절하게 풀 수 있다. 이때 x는 0보다 크거나 같고 n보다 작고 y는 0보다 크거나 같고 m보다 작으면 반복문을 종료시킨다. 방향은 1~5번일 때 →로 시작하게..

티스토리툴바