본문 바로가기

알고리즘98

백준 g5 2170 선 긋기 c++ https://www.acmicpc.net/problem/2170 2170번: 선 긋기 첫째 줄에 선을 그은 횟수 N (1 ≤ N ≤ 1,000,000)이 주어진다. 다음 N개의 줄에는 선을 그을 때 선택한 두 점의 위치 x, y (-1,000,000,000 ≤ x < y ≤ 1,000,000,000)가 주어진다. www.acmicpc.net 문제 설명 선을 x~y까지 N개 그을 수 있다. 그어진 선 길이의 총합 구하기 단, 겹쳐진 선은 구분할 수 없다. 풀이 시작점을 기준으로 정렬을 하고, 만약 겹치는 구간이 있다면 포함시키면서 한 덩어리(?)를 확장시켜 나간다. 겹치는 구간이 끝나면 이미 정렬된 상태니까 그 덩어리는 끝난 것이므로 새로운 선에서 다시 시작한다. 처음에는 강의실 문제처럼 끝 점을 기준으.. 2024. 1. 26.
백준 s2 1541 잃어버린 괄호 c++ https://www.acmicpc.net/problem/1541 1541번: 잃어버린 괄호 첫째 줄에 식이 주어진다. 식은 ‘0’~‘9’, ‘+’, 그리고 ‘-’만으로 이루어져 있고, 가장 처음과 마지막 문자는 숫자이다. 그리고 연속해서 두 개 이상의 연산자가 나타나지 않고, 5자리보다 www.acmicpc.net 풀이 처음에는 괄호를 한 번만 칠 수 있는 줄 알고 이걸 어떻게 그리디로 풀지 .. 고민했으나 괄호는 그냥 마음대로 칠 수 있는 거였다. 괄호를 제한없이 칠 수 있으면, -뒤에 오는 숫자들에 괄호를 쳐서 최대한 많이 빼주면 최솟값이 될 거라 예상할 수 있다. -뒤에 오는 +들에 괄호를 치면 -를 분배한 것들과 같다. 다음 -가 오기전까지 +들을 묶어서 빼줄 값이 최대가 되도록 하면 된다. 코.. 2024. 1. 25.
백준 s4 11399 ATM c++ https://www.acmicpc.net/problem/11399 11399번: ATM 첫째 줄에 사람의 수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄에는 각 사람이 돈을 인출하는데 걸리는 시간 Pi가 주어진다. (1 ≤ Pi ≤ 1,000) www.acmicpc.net 풀이 총 걸리는 시간 = 각 사람들의 출금 시간 + 기다리는 시간 이때, 각 사람들의 출금 시간은 정해져 있으므로, 기다리는 시간을 최소로 하면 된다. 기다리는 시간을 최소로 하는 방법은 출금 시간이 짧은 사람들부터 순서대로 하는 것이다. /*boj s4 11300 ATM*/ #include #include #define MAXN 1005 using namespace std; int N; int arr[MAXN]; int ma.. 2024. 1. 25.
백준 s4 1026 보물 c++ https://www.acmicpc.net/problem/1026 1026번: 보물 첫째 줄에 N이 주어진다. 둘째 줄에는 A에 있는 N개의 수가 순서대로 주어지고, 셋째 줄에는 B에 있는 수가 순서대로 주어진다. N은 50보다 작거나 같은 자연수이고, A와 B의 각 원소는 100보다 작거 www.acmicpc.net 풀이 A, B 두 배열을 곱해서 구할 수 있는 최솟값은 B의 가장 큰 수에 A의 가장 작은 수를 곱하는 것이다. B는 재배열하면 안 된다고 했지만 A의 순서를 마음대로 바꿀 수 있기 때문에 사실상 상관 없음 A, B 둘다 정렬해준 후 가장 큰 수*가장 작은 수 끼리 곱해주면 된다. 전체 코드 /*boj g4 1920 수 찾기*/ #include #include #define MAXN 55 .. 2024. 1. 25.
백준 s4 2217 로프 c++ https://www.acmicpc.net/problem/2217 2217번: 로프 N(1 ≤ N ≤ 100,000)개의 로프가 있다. 이 로프를 이용하여 이런 저런 물체를 들어올릴 수 있다. 각각의 로프는 그 굵기나 길이가 다르기 때문에 들 수 있는 물체의 중량이 서로 다를 수도 있다. 하 www.acmicpc.net 풀이는 여기 참고 https://blog.encrypted.gg/975 /*boj s4 2217 로프*/ #include #include #define MAXN 100005 using namespace std; int N; int w[MAXN]; int main(void) { ios::sync_with_stdio(0); cin.tie(0); cin >> N; for (int i = 0; .. 2024. 1. 25.
백준 p5 19235 모노미노도미노 c++ https://www.acmicpc.net/problem/19235 19235번: 모노미노도미노 모노미노도미노는 아래와 같이 생긴 보드에서 진행되는 게임이다. 보드는 빨간색 보드, 파란색 보드, 초록색 보드가 그림과 같이 붙어있는 형태이다. 게임에서 사용하는 좌표 (x, y)에서 x는 행, www.acmicpc.net 문제 설명 전반적인 내용은 모노미노도미노 2와 같다(https://kyj0032.tistory.com/40). 달라진 점은 행이 삭제될 때, 중력의 영향을 받아 블록들이 밑으로 내려온다는 것 1. 이때 2*1이나 1*2 크기의 블록들은 하나로 쳐서, 한 칸만 밑으로 내려오는 경우는 없다. 2. 또한, 지워야 할 행이 2줄 이상일 때는 한 줄 지우고 떨어뜨리고 한 줄 지우고 떨어뜨리고 .. .. 2024. 1. 24.
백준 g2 20061 모노미노도미노 2 c++ https://www.acmicpc.net/problem/20061 20061번: 모노미노도미노 2 모노미노도미노는 아래와 같이 생긴 보드에서 진행되는 게임이다. 보드는 빨간색 보드, 파란색 보드, 초록색 보드가 그림과 같이 붙어있는 형태이다. 게임에서 사용하는 좌표 (x, y)에서 x는 행, www.acmicpc.net 문제 설명 빨강, 파랑, 초록으로 나뉘어진 특수한 보드가 있다. 빨간색 보드에 1*1, 2*1, 1*2인 블록을 놓을 수 있으며, 이는 파랑, 초록 보드에도 같이 놓여진다. 파랑, 초록에 놓여질 때는 슬라이딩 하듯이 놓을 수 있는 가장 끝에 놓아진다. 한 행/열에 4칸이 모두 차면, 그 줄은 사라지고 점수를 1점 얻는다. 해당 줄이 사라지면 그 위에 줄이 그대로 내려온다. 파랑, 초록 .. 2024. 1. 23.
백준 g1 4991 로봇 청소기 c++ https://www.acmicpc.net/problem/4991 4991번: 로봇 청소기 각각의 테스트 케이스마다 더러운 칸을 모두 깨끗한 칸으로 바꾸는 이동 횟수의 최솟값을 한 줄에 하나씩 출력한다. 만약, 방문할 수 없는 더러운 칸이 존재하는 경우에는 -1을 출력한다. www.acmicpc.net 문제 설명 M, N 크기의 방에 *: 더러운 칸, x: 가구, o: 로봇 청소기의 시작 위치가 존재한다. 더러운 칸의 개수는 10개를 넘지 않으며, 방 크기는 최대 20*20이다. 로봇청소기 시작 위치에서 더러운 칸을 모두 깨끗한 칸으로 청소할 때, 이동횟수의 최솟값 구하기 방문했던 곳 다시 방문 가능 풀이 1. 먼지의 개수가 10개 이하이므로, 무슨 먼지부터 청소할 건지 정하는 순열(10!)을 구한다. .. 2024. 1. 23.
백준 g2 17825 주사위 윷놀이 c++ https://www.acmicpc.net/problem/17825 17825번: 주사위 윷놀이 주사위 윷놀이는 다음과 같은 게임판에서 하는 게임이다. 처음에는 시작 칸에 말 4개가 있다. 말은 게임판에 그려진 화살표의 방향대로만 이동할 수 있다. 말이 파란색 칸에서 이동을 시작하면 www.acmicpc.net 문제 설명 말은 시작 칸에 총 4개 파란색 칸에 멈추면, 파란색 화살표를 따라 가야 함 말이 이동을 마치는 칸(도착점)에 다른 말이 있으면 X 말이 이동을 마칠 때마다 칸에 적혀 있는 수가 점수로 추가됨 주사위에서 나올 수 10개가 주어질 때, 얻을 수 있는 점수의 최댓값 풀이 1.주사위 판 짜기 빨간 화살표만 따라갔을 때 경로 0, 10에 도착한 경우 경로 1, 20에 도착한 경우 경로 2, 3.. 2024. 1. 22.

티스토리툴바