본문 바로가기

Algorithm/BOJ

(13)
[백준 15489] 파스칼 삼각형 백준 15489번 : 파스칼 삼각형 https://www.acmicpc.net/problem/15489 15489번: 파스칼 삼각형 첫째 줄에 양의 정수 R, C, W가 공백을 한 칸씩 두고 차례로 주어진다. (단, 2 ≤ R+W ≤ 30, 2 ≤ C+W ≤ 30, 1 ≤ W ≤ 29, C ≤ R) www.acmicpc.net /* 문제 설명 */ 파스칼 삼각형은 양 끝을 제외한 각 수는 자신의 바로 왼쪽 위의 수와 바로 오른쪽 위의 수의 합으로 되어있다. 이때 R번째 줄, C번째 수를 위 꼭짓점으로 하는 한 변이 포함하는 수의 개수가 W인 정삼각형과 그 내부를 생각하자. 정삼각형의 변과 그 내부에 있는 수들의 합을 구하여라. /* 해결 방안 */ 현재 5번째 줄 3번째 칸에 있다면, 이는 4번째 줄 2..
[백준 1756] 피자 굽기 백준 1756번 : 피자 굽기 www.acmicpc.net/problem/1756 1756번: 피자 굽기 첫째 줄에 오븐의 깊이 D와 피자 반죽의 개수 N이 공백을 사이에 두고 주어진다. (1 2 첫 번째 피자인 지름 3짜리를 오븐에 넣으면,6번째 관이 2이므로 5번째 관에 들어가게 된다. 위와 같이 배열의 처음부터 시작해서 끝까지 가는 도중에, 현재 피자보다 지름이 작은 관을 만나게 되면 그 곳에 안착하게 된다. 따라서 5 6 4 3 6 2 3 에서 마지막 관이 3이라 한들, 자신의 위에 있는 지름 2짜리의 관에 막혀버리게 되는 것이다. 즉, 배열이 5 6 4 3 6 2 3 이렇게 있지만, 배열의 각 요소들은 자신보다 위(왼쪽)에 있는 관의 지름에 영향을 받으므로, 5 5 4 3 3 2 2 와 같이 동..
[백준 18238] ZOAC 2 백준 18238번 : ZOAC 2 www.acmicpc.net/problem/9440 9440번: 숫자 더하기 강민이가 초등학교 3학년일 때, 담임선생님이 이런 문제를 냈었다. 숫자 1, 2, 7, 8, 9 를 사용해서 만든 두 숫자를 더했을 때, 나올 수 있는 가장 작은 수는 무엇일까요? 강민이는 이 문제의 답이 2 www.acmicpc.net /* 문제 설명 */ 위의 그림과 같이, 원판에 문자들이 A-Z 순서대로 적혀있다. 원판을 왼쪽 또는 오른쪽으로 한 칸 돌리는 데에 1의 시간이 소요된다. 처음에는 화살표가 'A'를 가리키고 있을 때, 주어진 문자열을 원판을 적절하게 움직여 최대한 빠르게 출력하시오. /* 해결 방안 */ 원판을 오른쪽이나 왼쪽으로 돌릴 수 있기 때문에, A에서 B로 갈 수도 있..
[백준 9440] 숫자 더하기 백준 9440번 : 숫자 더하기 www.acmicpc.net/problem/9440 9440번: 숫자 더하기 강민이가 초등학교 3학년일 때, 담임선생님이 이런 문제를 냈었다. 숫자 1, 2, 7, 8, 9 를 사용해서 만든 두 숫자를 더했을 때, 나올 수 있는 가장 작은 수는 무엇일까요? 강민이는 이 문제의 답이 2 www.acmicpc.net /* 문제 설명 */ N(2 ≤ N ≤ 14)개의 0~9 사이의 숫자가 주어질 때, 숫자들을 조합하여 우선 두 개의 숫자를 만든다. 만든 두 숫자를 더했을 때, 나올 수 있는 가장 작은 수를 구하시오. /* 해결 방안 */ 두 숫자를 더했을 때, 최소가 되려면 어떻게 해야할까? 숫자의 앞에서 부터 뒤를 봤을 때, 큰 숫자를 어디로 배치해야할지 떠올려보자. 큰 숫자..
[백준 14939] 불 끄기 백준 14939번 : 불 끄기 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 /* 문제 설명 */ 전구 켜져 있다 == 1, 꺼져 있다 == 0 10×10 배열이 있을 때, 한 칸을 누르면 그 위치에서 위, 아래, 왼쪽, 오른쪽에 있는 배열의 상태가 바뀌게 된다. 모든 배열을 0으로 만들기 위해서는 최소 몇 번 눌러야 하는가? /* 해결 방안 */ 가로가 10칸이고, 세로가 10칸 이므로, 총 100칸에 대해서 클릭할지 말지를 ..
[백준 17609] 회문 백준 17609번 : 회문 www.acmicpc.net/problem/17609 17609번: 회문 각 문자열이 회문인지, 유사 회문인지, 둘 모두 해당되지 않는지를 판단하여 회문이면 0, 유사 회문이면 1, 둘 모두 아니면 2를 순서대로 한 줄에 하나씩 출력한다. www.acmicpc.net /* 문제 설명 */ 문자열이 입력으로 주어질 때, 이를 분석하여 0. 회문 : 앞 뒤 방향으로 볼 때 같은 순서의 문자로 구성된 문자열 1. 유사 회문 : 회문이 아니지만 한 문자를 삭제하여 회문으로 만들 수 있는 문자열 2. 회문도, 유사 회문도 아닌 것 셋 중 무엇인지 출력하라. /* 해결 방안 */ 현재 보고 있는 글자를 삭제하는 경우와 유지하는 경우에 대해 따져봐야한다. → 이를 쉽게하기 위해 함수를 이용..
[백준 11501] 주식 백준 11501번 : 주식 www.acmicpc.net/problem/11501 11501번: 주식 입력의 첫 줄에는 테스트케이스 수를 나타내는 자연수 T가 주어진다. 각 테스트케이스 별로 첫 줄에는 날의 수를 나타내는 자연수 N(2 ≤ N ≤ 1,000,000)이 주어지고, 둘째 줄에는 날 별 주가를 나타 www.acmicpc.net /* 문제 설명 */ 매일, 세가지 행동 중 하나를 한다. 1. 주식을 하나 산다. 2. 원하는 만큼 가지고 있는 주식을 판다. 3. 아무것도 안한다. 이 때, 최대 이익이 어떻게 되는지 구하시오. /* 해결 방안 */ 주가가 낮을 때는 주식을 사야되고, 높을 때는 팔아야 된다. 따라서 최고점일 때 최대한 많이 팔 수 있도록, 최고점보다 낮은 주가를 만날 경우에는 무조건 ..
[백준 1311] 할 일 정하기1 백준 1311번 : 할 일 정하기1 www.acmicpc.net/problem/1311 1311번: 할 일 정하기 1 N명의 사람과 N개의 일이 있다. 각 사람은 일을 하나 담당해야 하고, 각 일을 담당하는 사람은 한 명 이어야 한다. 또한, 모든 사람은 모든 일을 할 능력이 있다. 사람은 1번부터 N번까지 번호가 매 www.acmicpc.net /* 문제 설명 */ N명의 사람과 N개의 일이 있다. 각 사람은 일을 하나 담당해야 하고, 각 일을 담당하는 사람은 한 명 이어야 한다. Dij를 i번 사람이 j번 일을 할 때 필요한 비용이라고 했을 때, 모든 일을 하는데 필요한 비용의 최솟값을 구하여라. /* 해결 방안 */ N명의 사람들과 N개의 일이 있고, 각각의 사람들이 j번 일을 할 때 필요한 비용이..
[백준 2170] 선 긋기 백준 2170번 : 선 긋기 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 /* 문제 설명 */ 여러 번 그은 곳과 한 번 그은 곳의 차이를 구별할 수 없을 때, 그려진 선들의 총 길이를 구하시오. (선이 여러 번 그려진 곳은 한 번씩만 계산한다.) /* 해결 방안 */ 겹쳐진 선분들끼리 한 구간으로 합쳐나가다가, 마지막에 구간들의 길이만 세서 더해주자! → Sweeping /* 구현 과정 */ 1. 왼쪽 좌표를 기준으로 선을 ..
[백준 20058] 마법사 상어와 파이어스톰 백준 20058번 : 마법사 상어와 파이어스톰 www.acmicpc.net/problem/20058 20058번: 마법사 상어와 파이어스톰 마법사 상어는 파이어볼과 토네이도를 조합해 파이어스톰을 시전할 수 있다. 오늘은 파이어스톰을 크기가 2N × 2N인 격자로 나누어진 얼음판에서 연습하려고 한다. 위치 (r, c)는 격자의 r행 c www.acmicpc.net /* 문제 설명 */ 2N × 2N 격자의 얼음판을 2L × 2L 크기의 부분 격자로 나눈다. 그 후, 모든 부분 격자를 시계 방향으로 90도 회전시킨다. 이후 얼음이 있는 칸 3개 또는 그 이상과 인접해있지 않은 칸의 얼음을 -1 해준다. 위의 행동을 Q번 할 때, 모든 파이어스톰을 시전한 후에 남아있는 얼음 A[r][c]의 합과 남아있는 얼음..