반응형

백준 29

[백준 자바] 16173번 점프왕 쩰리(small)

문제쩰리’는 점프하는 것을 좋아하는 젤리다. 단순히 점프하는 것에 지루함을 느낀 ‘쩰리’는 새로운 점프 게임을 해보고 싶어 한다. 새로운 점프 게임의 조건은 다음과 같다.‘쩰리’는 가로와 세로의 칸수가 같은 정사각형의 구역 내부에서만 움직일 수 있다. ‘쩰리’가 정사각형 구역의 외부로 나가는 경우엔 바닥으로 떨어져 즉시 게임에서 패배하게 된다.‘쩰리’의 출발점은 항상 정사각형의 가장 왼쪽, 가장 위의 칸이다. 다른 출발점에서는 출발하지 않는다.‘쩰리’가 이동 가능한 방향은 오른쪽과 아래 뿐이다. 위쪽과 왼쪽으로는 이동할 수 없다.‘쩰리’가 가장 오른쪽, 가장 아래 칸에 도달하는 순간, 그 즉시 ‘쩰리’의 승리로 게임은 종료된다.‘쩰리’가 한 번에 이동할 수 있는 칸의 수는, 현재 밟고 있는 칸에 쓰여 있..

[백준 2473 자바] 세 용액

[백준 2473 자바] 세 용액문제여러 종류의 산성 용액과 알칼리성 용액을 보유하고 있다.각 용액에는 그 용액의 특성을 나타내는 하나의 정수가 주어진다.산용 용액은 1부터 1,000,000,000까지의 양의 정수, 알칼리성 용액의 특성은 -1부터 -1,000,000,000까지의 음의 정수로 나타낸다. 같은 양의 세 가지 용액을 혼합한 용액의 특성값은 혼합에 사용된 각 용액의 특성값의 합으로 정의한다.세 용의 혼합하여 특성값이 0에 가장 가까운 용액을 만들려고 할 때0에 가장 가까운 용액을 만드는 세 용액을 찾는 프로그램을 작성하시오. 입력첫째 줄에는 전체 용액이 수 n이 입력된다 n은 3 이상 5000 이하의 정수이다.둘째 줄에는 용액의 특성값을 나타내는 n개의 정수들이 빈값을 사이에 두고 주어진다.모..

[백준 3184 자바] 양

3184번 양문제미키의 뒷마당에는 특정 수의 양이 있다. 늑대는 마당에 들어와 양을 공격했다.마당은 행과 열로 이루어진 직사각형 모양이다.글자 '.' (점)은 빈 필드를 의미하며, 글자 '#'는 울타리, 'o'는 양 'v'는 늑대를 의미한다.한 칸에서 수평, 수직만으로 이동하며 울타리를 지나지 않고 다른 칸으로 이동할 수 있다면 두 칸은 같은 영역 안에 속해 있다고 한다.마당에서 탈출 할 수 있는 칸은 어떤 영역에도 속하지 않는다고 간주한다. 양은 늑대에게 싸움을 걸 수 있고 영역 안에 양의 수가 늑대의 수보다 많다면 이기고, 늑대를 우리에서 쫓아낸다.그렇지 않다면 늑대가 그 지역 안의 모든 양을 먹는다.맨 처음 모든 양과 늑대는 마당 안 영역에 존재한다.아침이 도달했을 때 살아남은 양과 늑대의 수를 출..

[백준 5639 자바] 이진 검색 트리

[백준 5639 자바] 이진 검색 트리문제이진 검색 트리는 다음과 같은 세 가지 조건을 만족하는 이진트리이다.노드의 왼쪽 서브트리에 있는 모든 노드의 키는 노드의 키보다 작다.노드의 오른쪽 서브트리에 있는 모든 노드의 키는 노드의 키보다 크다.왼쪽, 오른쪽 서브트리도 이진 검색 트리이다.전위 순회 (루트-왼쪽-오른쪽)은 루트를 방문하고, 왼쪽 서브트리, 오른쪽 서브 트리를 순서대로 방문하면서 노드의 키를 출력한다. 후위 순회 (왼쪽-오른쪽-루트)는 왼쪽 서브트리, 오른쪽 서브트리, 루트 노드 순서대로 키를 출력한다. 예를 들어, 위의 이진 검색 트리의 전위 순회 결과는 50 30 24 5 28 45 98 52 60이고, 후위 순회 결과는 5 28 24 45 30 60 52 98 50이다.이진 검색 트리를..

[백준 16964 파이썬] DFS 스페셜 저지

백준 16964 파이썬DFS 스페셜 저지문제BOJ에서 정답이 여러 가지인 경우에는 스페셜 저지를 사용 한다.스페셜 저지는 유저가 출력한 답을 검증하는 코드를 통해서 정답 유무를 결정하는 방식이다.오늘은 스페셜 저지 코드를 하나 만들어 보려고 한다.정점의 개수 N이고 정점에 1부터 N까지 번호가 매겨져 있는 양방향 그래프가 있을 때, DFS 알고리즘은 다음과 같은 형태로 이루어져 있다.이 문제에서 시작 정점은 1이기 때문에 가장 처음에 호출하는 함수는 dfs(1)이다.DFS 방문 순서는 dfs 함수에서 //x를 방문이라고 적힌 곳에 도착한 정점 번호를 순서대로 나열한 것이다.트리가 주어졌을 때, 올바른 DFS 방문 순서인지 구하여라.입력첫째 줄에 정점수 N 이 주어진다.둘째 줄부터는 N-1개의 줄에는 트리..

[파이썬] 백준 3190 뱀

[파이썬] 백준 3190 뱀https://www.acmicpc.net/problem/3190 문제Dummy라는 도스 게임이 있다. 이 게임에는 뱀이 나와서 기어 다니는데 , 사과를 먹으면 뱀 길이가 늘어난다.뱀이 벽 또는 자기 자신의 몸과 부딪히면 게임이 끝이 난다. N x N 정사각 보드 위에서 진행되고 몇몇 칸에 사과가 놓여 있다. 보드 상하좌우 끝에는 벽이 있다.뱀의 처음 시작위치는 맨 위 맨 좌측에 위치하고 처음 길이는 1이다. 뱀은 처음에는 오른쪽으로 향한다. 뱀은 매초 마다 움직이는데 아래의 규칙을 따른다.먼저 뱀은 몸길이를 늘려 머리를 다음칸에 위치시킨다.만약 벽이나 자기 자신의 몸과 부딪히면 게임이 끝난다.만약 이동한 칸에 사과가 있다면, 그 칸에 있던 사과가 없어지고 꼬리는 움직이지 않는..

[백준 파이썬] 1389 케빈 베이컨의 6단계 법칙

[백준 파이썬] 1389 케빈 베이컨의 6단계 법칙 문제케빈 베이컨의 6단계 법칙에 의하면 지구에 있는 모든 사람들은 최대 6단계 이내에서 서로 아는 사람으로 연결될 수 있다.케빈 베이컨 게임은 임의의 두 사람이 최소 몇 단계 만에 이어질 수 있는지 계산하는 게임이으로 이 게임을 했을 때 모든 사람 나오는 단계의 총 합을 케빈 베이컨의 수라고 할 때 이때 이 수가 가장 적은 사람을 찾는 문제이다. 이때 단계를 계산하는 방법으로 유저가 5명이고, 1과 3, 1과 4, 2와 3, 3과 4, 4와 5가 친구인 경우를 생각해 보자.1은 2까지 3을 통해 2단계 만에 연결될 수 있으며, 3까지는 1단계 , 4까지 1단계 , 5까지는 4를 통해 2단계만에 연결된다그러면 케빈 베이컨의 수는 2+1+1+2 = 6이다...

[백준 파이썬] 2579 계단오르기

[백준 파이썬] 2579 계단 오르기문제계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에서 위치한 도착지점까지 가는 게임이다.각 계단에는 일정한 점수가 쓰여 있고 그 계단을 밝으면 점수를 얻게 된다.이때 총점수의 최댓값을 구해야 하면 아래의 규칙을 지켜야 한다. 계단은 한 번에 한 계단씩 또는 두 계단씩 오를 수 있다. 즉, 한 계단을 밟으면서 이어서 다음 계단이나, 다음다음 계단으로 오를 수 있다.연속된 세 개의 계단을 모두 밟아서는 안 된다. 단, 시작점은 계단에 포함되지 않는다.마지막 도착 계단은 반드시 밟아야 한다.위그림의 예를 가지고 풀어본다면첫 번째 계단 => 두 번째 계단 => 네 번째 계단 => 다섯 번째 계단 밟으면 최댓값이 나온다.  풀이이 문제를 풀기 위해서 해야 할 첫 번째 생..

[백준 파이썬] 2749 피보나치 수 3

[백준 파이썬] 2749 피보나치 수 3  처음에는 이게 무슨 골드 2 문제지 하고dp=[0,1]n=int(input())for i in range(2,n+1): dp.append((dp[i-1]+dp[i-2])%1000000)print(dp[n])이렇게 코드를 제출했다 결과는 메모리 초과로 실패하여 문제 조건을 확인하였다입력이 1,000,000,000,000,000,000 작은 n에 대한 피보나치수열인데 메모리 제한이 128MB였다.문제 답을 출력할 때 1,000,000으로 나눈 나머지를 출력한다라고 적혀있었다.이걸 보고 난 반복되는 주기가 발생할겠다고 생각하여 dp=[0,1]n=int(input())for i in range(2,4500000+1): dp.append((dp[i-1]+dp[..

[배준 파이썬]2564 경비원

문제동근이는 무인 경비 회사 경비원으로 항상 대기하고 있다가 호출이 들어오면 그곳으로 가야 한다 이때 블록을 가로질러갈 수 없다 그렇기에 1번 에서 호출이 들어올 경우 x에서 출발하여 1번까가는 거리는 시계방향으로 갈경우 12, 반시계 방향으로 갈 경우 18이 된다.2번에서 호출이 들어올 경우 최단거리는 6이고 3번은 5가 된다 이때 각 상점  사이의 최단 거리의 합을 구하는 프로그램을 작성하시오.입력첫 번째 줄에의 블록의 가로 길이와 세로 길이가 주어진다.둘째 줄에는 상점의 개수가 주어진다.그다음 줄부터는 상점의 위치가 주어지는데  첫번째 수는 1은 북, 2는 남, 3은 서 , 4,는 동쪽을 의미하며 두 번째는 상점의 위치를 의미한다.그리고 마지막 둘은 동근의 위치를 상점 위치과 같이 나타낸다. 출력첫..

반응형