![]()
문제 링크 : https://www.acmicpc.net/problem/13975 13975번: 파일 합치기 3 프로그램은 표준 입력에서 입력 데이터를 받는다. 프로그램의 입력은 T개의 테스트 데이터로 이루어져 있는데, T는 입력의 맨 첫 줄에 주어진다.각 테스트 데이터는 두 개의 행으로 주어지는데, 첫 행에는 소설을 구성하는 장의 수를 나타내는 양의 정수 K (3 ≤ K ≤ 1,000,000)가 주어진다. 두 번째 행에는 1장부터 K장까지 수록한 파일의 크기를 나타내는 양의 정수 K개가 주어진다. 파일의 크기는 10,000을 초과하지 않는다. www.acmicpc.net 문제 설명 백준 11066번 파일 합치기 1 : https://suhwanc.tistory.com/76 와 같은 문제인데, 이 문제는..
![]()
문제 링크 : https://www.acmicpc.net/problem/11066 11066번: 파일 합치기 문제 소설가인 김대전은 소설을 여러 장(chapter)으로 나누어 쓰는데, 각 장은 각각 다른 파일에 저장하곤 한다. 소설의 모든 장을 쓰고 나서는 각 장이 쓰여진 파일을 합쳐서 최종적으로 소설의 완성본이 들어있는 한 개의 파일을 만든다. 이 과정에서 두 개의 파일을 합쳐서 하나의 임시파일을 만들고, 이 임시파일이나 원래의 파일을 계속 두 개씩 합쳐서 소설의 여러 장들이 연속이 되도록 파일을 합쳐나가고, 최종적으로는 하나의 파일로 합친다. 두 개의 파일을 www.acmicpc.net 문제 요약 여러 파일들이 주어졌을 때 파일들을 두 개씩 합쳐서 여러 장들이 연속이 되도록 파일을 합쳐나가 최종적으로..
![]()
문제 링크 : https://www.acmicpc.net/problem/2252 문제 요약 N명의 학생들을 키 순서대로 줄을 세우되, 모든 학생들을 다 비교해보는게 아닌 두 명씩 일부 학생들의 키를 비교한다. 입력에서 주어지는 A,B 쌍은 키 순서대로 주어지고, 학생들의 번호는 1부터 N번이다. 풀이 위상 정렬 문제입니다. 위상 정렬이란 ? https://suhwanc.tistory.com/74 위상 정렬 위상 정렬은 그래프의 간선 u, v (이 문제에선 a,b 쌍을 말한다) 이 u가 v보다 먼저일 때 정점의 순서를 찾는 알고리즘입니다. 위상 정렬을 구현할 때는 bfs를 사용합니다! 예를 들어 이런식으로 구성된 그래프가.. suhwanc.tistory.com 위상 정렬은 그래프의 간선 u, v (이 문제..
![]()
문제 링크 : https://www.acmicpc.net/problem/14503 14503번: 로봇 청소기 로봇 청소기가 주어졌을 때, 청소하는 영역의 개수를 구하는 프로그램을 작성하시오. 로봇 청소기가 있는 장소는 N×M 크기의 직사각형으로 나타낼 수 있으며, 1×1크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 벽 또는 빈 칸이다. 청소기는 바라보는 방향이 있으며, 이 방향은 동, 서, 남, 북중 하나이다. 지도의 각 칸은 (r, c)로 나타낼 수 있고, r은 북쪽으로부터 떨어진 칸의 개수, c는 서쪽으로 부터 떨어진 칸의 개수이다. 로봇 청소기는 다음 www.acmicpc.net 풀이 시뮬레이션 문제입니다! 이 문제는 조건이 조금 까다로운데, 나는 4가지 조건 중 c,d 번 먼저 해결하려고 하..
![]()
문제 링크 : https://www.acmicpc.net/problem/14499 14499번: 주사위 굴리기 첫째 줄에 지도의 세로 크기 N, 가로 크기 M (1 ≤ N, M ≤ 20), 주사위를 놓은 곳의 좌표 x y(0 ≤ x ≤ N-1, 0 ≤ y ≤ M-1), 그리고 명령의 개수 K (1 ≤ K ≤ 1,000)가 주어진다. 둘째 줄부터 N개의 줄에 지도에 쓰여 있는 수가 북쪽부터 남쪽으로, 각 줄은 서쪽부터 동쪽 순서대로 주어진다. 주사위를 놓은 칸에 쓰여 있는 수는 항상 0이다. 지도의 각 칸에 쓰여 있는 수는 10을 넘지 않는 자연수 또는 0이다. 마 www.acmicpc.net 풀이 시뮬레이션 문제입니다! 시뮬레이션 문제답게 이 문제는 주사위를 구현하는 문제이다. 다행히 이 문제에서 주사위..
![]()
문제 링크 : https://www.acmicpc.net/problem/15658 15658번: 연산자 끼워넣기 (2) 첫째 줄에 수의 개수 N(2 ≤ N ≤ 11)가 주어진다. 둘째 줄에는 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 100) 셋째 줄에는 합이 N-1보다 크거나 같고, 4N보다 작거나 같은 4개의 정수가 주어지는데, 차례대로 덧셈(+)의 개수, 뺄셈(-)의 개수, 곱셈(×)의 개수, 나눗셈(÷)의 개수이다. www.acmicpc.net 풀이 브루트 포스 문제입니다! 문제 난이도에 비해 생각보다 쉽지 않아서 많이 고전했던 문제이다. 이 문제는 개인적으로는 그 전 시리즈 문제 (BOJ 14888번 연산자 끼워넣기 https://www.acmicpc.net/problem/148..
![]()
문제 링크 : https://www.acmicpc.net/problem/1248 1248번: 맞춰봐 문제 규현이는 멍청하다. 왜냐하면, 1~10까지 수 밖에 모르기 때문이다. 어느 날 규현이 옆을 지나가던 태석이가 규현이를 보고 이렇게 외쳤다. "빵빵!!" 규현이는 "아하!" 하면서 세상에는 빵이란 수도 있구나 했다. 그날 이후로 규현이는 매일 친구들을 볼 때면 "빵빵!!" 거리면서 인사를 했다. 규현이의 친구 중에는 태방이가 있다. 자꾸 규현이가 "빵빵!!" 거릴때 마다 자신을 놀리는 것 처럼 생각했던 태방이는 규현이에게 그건 "빵이 아니고 영이야" www.acmicpc.net 풀이 백트래킹 문제입니다! 이 문제는 서론이 좀 긴데 간단히 압축하자면, -10~10 까지의 정수로 채운 S배열이 있는데, S..
![]()
문제 링크 : https://www.acmicpc.net/problem/15661 15661번: 링크와 스타트 첫째 줄에 N(4 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에 S가 주어진다. 각 줄은 N개의 수로 이루어져 있고, i번 줄의 j번째 수는 Sij 이다. Sii는 항상 0이고, 나머지 Sij는 1보다 크거나 같고, 100보다 작거나 같은 정수이다. www.acmicpc.net 풀이 Brute force 문제 입니다! 이 문제는 선수들이 몇명씩 나뉘는지 모르기 때문에 순열로 풀 수 없고 팀을 두 개로 나눈 후 재귀호출을 통해서 선수들을 두 팀에 각각 집어 넣는 과정을 반복합니다. 이 때 재귀호출 함수의 인자로는 0~n까지 선수가 들어가는지에 대한 index와 두 팀의 선수들을 구성하는 ..
![]()
문제 링크 : https://www.acmicpc.net/problem/9019 9019번: DSLR 문제 네 개의 명령어 D, S, L, R 을 이용하는 간단한 계산기가 있다. 이 계산기에는 레지스터가 하나 있는데, 이 레지스터에는 0 이상 10,000 미만의 십진수를 저장할 수 있다. 각 명령어는 이 레지스터에 저장된 n을 다음과 같이 변환한다. n의 네 자릿수를 d1, d2, d3, d4라고 하자(즉 n = ((d1 × 10 + d2) × 10 + d3) × 10 + d4라고 하자) D: D 는 n을 두 배로 바꾼다. 결과 값이 9999 보다 큰 경 www.acmicpc.net 풀이 Bfs 문제입니다! 문제에 나와있듯 가지치기의 방법은 4가지가 있고, 출력에서 최소한의 명령어 나열을 요구했으므로 문..
![]()
문제 링크 : https://www.acmicpc.net/problem/1697 1697번: 숨바꼭질 문제 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 1초 후에 2*X의 위치로 이동하게 된다. 수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 www.acmicpc.net 풀이 bfs 문제입니다! 수빈이의 이동 방법이 3가지이고, n과 k의 범위가 0~10만 이기 때문에, 이 문제는 최대 10만..
![]()
문제 링크 : https://www.acmicpc.net/problem/17404 17404번: RGB거리 2 RGB거리에 사는 사람들은 집을 빨강, 초록, 파랑중에 하나로 칠하려고 한다. 또한, 그들은 모든 이웃은 같은 색으로 칠할 수 없다는 규칙도 정했다. 집 i의 이웃은 집 i-1과 집 i+1이고, 첫 집과 마지막 집도 이웃이다. 각 집을 빨강으로 칠할 때 드는 비용, 초록으로 칠할 때 드는 비용, 파랑으로 드는 비용이 주어질 때, 모든 집을 칠하는 비용의 최솟값을 구하는 프로그램을 작성하시오. www.acmicpc.net 풀이 다이내믹 프로그래밍 문제입니다! RGB거리에 사는 사람들은 빨강, 초록, 파랑 3가지 색 중 하나로 집을 칠해야하는데, 인접한 집의 색이 같으면 안된다. 따라서 i번째 집의..
![]()
문제 링크 : https://www.acmicpc.net/problem/1309 1309번: 동물원 첫째 줄에 우리의 크기 N(1≤N≤100,000)이 주어진다. www.acmicpc.net 풀이 다이내믹 프로그래밍 문제입니다! 2X1 칸에 사자를 배치하는 경우는 왼쪽 사자 오른쪽 사자 사자 없음 세 가지이며, 사자들은 가로,세로에 붙어있을 수 없다. 각각의 경우를 0,1,2로 표현했을 경우 d[i][j] = i칸에 j상태의 사자가 있을 경우 사자 배치의 경우의 수 라고 표현 가능하며 각각 d[i][0] = d[i-1][1] + d[i-1][2] d[i][1] = d[i-1][0] + d[i-1][2] d[i][2] = d[i-1][0] + d[i-1][1] + d[i-1][2] 이다. 따라서 정답은 d..
