본문 바로가기

알고리즘346

[백준 2628] 종이자르기 (C++) https://www.acmicpc.net/problem/2628문제아래 과 같이 직사각형 모양의 종이가 있다. 이 종이는 가로방향과 세로 방향으로 1㎝마다 점선이 그어져 있다. 가로 점선은 위에서 아래로 1번부터 차례로 번호가 붙어 있고, 세로 점선은 왼쪽에서 오른쪽으로 번호가 붙어 있다. 점선을 따라 이 종이를 칼로 자르려고 한다. 가로 점선을 따라 자르는 경우는 종이의 왼쪽 끝에서 오른쪽 끝까지, 세로 점선인 경우는 위쪽 끝에서 아래쪽 끝까지 한 번에 자른다. 예를 들어, 의 가로 길이 10㎝이고 세로 길이 8㎝인 종이를 3번 가로 점선, 4번 세로 점선, 그리고 2번 가로 점선을 따라 자르면 와 같이 여러 개의 종이 조각으로 나뉘게 된다. 이때 가장 큰 종이 조각의 넓이는 30㎠이다. 입력으로 종.. 2024. 10. 12.
[백준 5639] 이진 검색 트리 (C++) https://www.acmicpc.net/problem/5639문제이진 검색 트리는 다음과 같은 세 가지 조건을 만족하는 이진 트리이다.노드의 왼쪽 서브트리에 있는 모든 노드의 키는 노드의 키보다 작다.노드의 오른쪽 서브트리에 있는 모든 노드의 키는 노드의 키보다 크다.왼쪽, 오른쪽 서브트리도 이진 검색 트리이다.전위 순회 (루트-왼쪽-오른쪽)은 루트를 방문하고, 왼쪽 서브트리, 오른쪽 서브 트리를 순서대로 방문하면서 노드의 키를 출력한다. 후위 순회 (왼쪽-오른쪽-루트)는 왼쪽 서브트리, 오른쪽 서브트리, 루트 노드 순서대로 키를 출력한다. 예를 들어, 위의 이진 검색 트리의 전위 순회 결과는 50 30 24 5 28 45 98 52 60 이고, 후위 순회 결과는 5 28 24 45 30 60 52 .. 2024. 10. 11.
[백준 11564] 점프왕 최준민 (C++) https://www.acmicpc.net/problem/11564문제준민이는 점프를 좋아한다. 창영이는 그의 점프력을 시험하기 위해 수직선을 하나 놓고, a 이상 b 이하의 모든 정수 좌표에 맛있는 초콜릿을 놓았다. 수직선은 아래의 그림과 같이 나타낼 수 있다.준민이는 항상 0에서 시작하며, 준민이의 점프력이 k 라면 한 번 점프를 하여 -k 나 +k 좌표에 도달한다. 준민이는 항상 점프 거리가 k가 되도록 점프를 한다. 만약 0의 위치에 초콜릿이 있다면, 준민이는 점프하기 전에 초콜릿을 일단 먹고 시작한다.초콜릿 중독자인 준민이는 모든 초콜릿을 얻기 위해 수직선에 올라섰다. 또한 준민이는 아침에 밥을 아주 많이 먹었기 때문에 무한번 점프 할 수 있다. 여러분이 해야하는 일은, k의 점프력을 가진 준민.. 2024. 10. 10.
[백준 1261] 알고스팟 (C++) https://www.acmicpc.net/problem/1261 문제알고스팟 운영진이 모두 미로에 갇혔다. 미로는 N*M 크기이며, 총 1*1크기의 방으로 이루어져 있다. 미로는 빈 방 또는 벽으로 이루어져 있고, 빈 방은 자유롭게 다닐 수 있지만, 벽은 부수지 않으면 이동할 수 없다.알고스팟 운영진은 여러명이지만, 항상 모두 같은 방에 있어야 한다. 즉, 여러 명이 다른 방에 있을 수는 없다. 어떤 방에서 이동할 수 있는 방은 상하좌우로 인접한 빈 방이다. 즉, 현재 운영진이 (x, y)에 있을 때, 이동할 수 있는 방은 (x+1, y), (x, y+1), (x-1, y), (x, y-1) 이다. 단, 미로의 밖으로 이동 할 수는 없다.벽은 평소에는 이동할 수 없지만, 알고스팟의 무기 AOJ를 이용해.. 2024. 10. 9.
[백준 10431] 줄세우기 (C++) https://www.acmicpc.net/problem/10431문제초등학교 선생님 강산이는 아이들을 데리고 단체로 어떤 일을 할 때 불편함이 없도록 새로 반에 배정받은 아이들에게 키 순서대로 번호를 부여한다. 번호를 부여할 땐 키가 가장 작은 아이가 1번, 그 다음이 2번, ... , 가장 큰 아이가 20번이 된다. 강산이네 반 아이들은 항상 20명이며, 다행히도 같은 키를 가진 학생은 한 명도 없어서 시간이 조금 지나면 아이들은 자기들의 번호를 인지하고 한 줄로 세우면 제대로 된 위치에 잘 서게 된다.하지만 매년 첫 며칠간 강산이와 강산이네 반 아이들은 자기가 키 순으로 몇 번째인지 잘 알지 못해 아주 혼란스럽다. 자기 위치를 찾지 못하는 아이들을 위해 강산이는 특별한 방법을 생각해냈다.우선 아무나.. 2024. 10. 8.
[백준 31589] 포도주 시음 (C++) https://www.acmicpc.net/problem/31589문제산들이는 포도주(와인)를 좋아한다. 그는 마트에서 팔고 있는 N종류의 포도주를 사서 음미하려고 한다. 포도주를 한 병 단위로 사기엔 산들이가 금전적으로 부담이 있기 때문에 그는 작은 용기에 담긴 포도주를 살 것이다. 마트에서 팔고 있는 N종류의 포도주들은 각각 T1, T2, …, TN의 맛을 갖고 있다. 맛의 값이 높은 포도주가 더 맛있는 포도주이다.산들이가 맛있는 포도주를 마시다가 맛없는 포도주를 마시면 그 맛이 감기약 맛을 방불케 하기 때문에 사실상 0의 맛을 느낀다. 하지만 맛없는 포도주를 마시다가 맛있는 포도주를 마시면 그 두 포도주의 맛 차이만큼 맛을 느낀다. 예외적으로 가장 먼저 마시는 포도주의 맛은 그 포도주 본연의 맛 그.. 2024. 10. 7.
[백준 22858] 원상 복구 (small) (C++) https://www.acmicpc.net/problem/22858문제 P1, P2, ⋯, PN의 수가 적혀 있는 N개의 카드가 있다.1부터 N까지 수가 하나씩 존재하는 수열 D1, D2, ⋯,Di, ⋯, DN이 있다. 이때 각 i에 대해 Di번째 카드를 i번째로 가져오는 작업을 셔플이라고 부른다.예를 들어, P1, P2, ⋯, PN이 1, 4, 5, 3, 2이고, D1, D2, ⋯, DN가 4, 3, 1, 2, 5라고 가정해보자. 이 카드를 한번 섞으면 3, 5, 1, 4, 2가 된다. 아래 그림에서 S는 카드를 한 번 섞은 후를 의미한다. 위 방식을 그대로 K번 셔플한 카드의 정보와 D의 정보를 알고 있다고 할 때, 원래 카드는 어떤 배치를 이루고 있었는지 구해보자.입력첫번째 줄에는 카드의 개수 N과.. 2024. 10. 6.
[백준 21318] 피아노 체조 (C++) https://www.acmicpc.net/problem/21318문제피아노를 사랑하는 시은이는 매일 아침 피아노 체조를 한다. 시은이는 N개의 악보를 가지고 있으며, 1번부터 N번까지의 번호로 부른다. 각 악보는 1 이상 109 이하의 정수로 표현되는 난이도를 가지고 있다. 난이도를 나타내는 수가 클수록 어려운 악보이다. 1 ≤ x ≤ y ≤ N 을 만족하는 두 정수 x, y를 골라 x번부터 y번까지의 악보를 번호 순서대로 연주하는 것이 피아노 체조이다.시은이는 피아노 체조를 할 때, 지금 연주하는 악보가 바로 다음에 연주할 악보보다 어렵다면 실수를 한다. 다시 말하자면, i(x ≤ i  y)번 악보의 난이도가 i + 1번 악보의 난이도보다 높다면 실수를 한다. 특히, 마지막으로 연주하는 y번 악보에선.. 2024. 10. 5.
[백준 14916] 거스름돈 (C++) https://www.acmicpc.net/problem/14916문제춘향이는 편의점 카운터에서 일한다.손님이 2원짜리와 5원짜리로만 거스름돈을 달라고 한다. 2원짜리 동전과 5원짜리 동전은 무한정 많이 가지고 있다. 동전의 개수가 최소가 되도록 거슬러 주어야 한다. 거스름돈이 n인 경우, 최소 동전의 개수가 몇 개인지 알려주는 프로그램을 작성하시오.예를 들어, 거스름돈이 15원이면 5원짜리 3개를, 거스름돈이 14원이면 5원짜리 2개와 2원짜리 2개로 총 4개를, 거스름돈이 13원이면 5원짜리 1개와 2원짜리 4개로 총 5개를 주어야 동전의 개수가 최소가 된다.입력첫째 줄에 거스름돈 액수 n(1 ≤ n ≤ 100,000)이 주어진다. 출력거스름돈 동전의 최소 개수를 출력한다. 만약 거슬러 줄 수 없으면.. 2024. 10. 4.

티스토리툴바