본문 바로가기
반응형

PS/백준

 (318)
[BOJ] 백준 1463 1로 만들기 (Swift) 문제 https://www.acmicpc.net/problem/1463 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net 풀이 이 문제는 1을 다른 해당 숫자로 만드는 방법의 최소 연산의 수를 구하는 것으로도 생각할 수 있습니다. 1은 1이니깐 0이고, 2는 1에서 1을 더해서 만들 수도 있고, 2를 곱해서도 만들 수 있으므로 최소 연산의 수는 1이고, 3은 1에서 1을 두번 더하는 방법과 3을 곱해서 만들 수 있습니다. 1을 두번 더하는 방법은 연산의 횟수가 2이기 때문에 3을 곱해서 만드는 연산을 1번 사용하는 것이 최소 연산의 수 일 것입니다. 4도 1에서 1을 세번 더하는 방법, 2에서 2를 곱하는 방법으로 나뉘게 됩..
[BOJ] 백준 2579 계단 오르기 (Swift) 문제 https://www.acmicpc.net/problem/2579 2579번: 계단 오르기 계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점 www.acmicpc.net 풀이 계단은 한번에 1칸 혹은 2칸씩 오를 수 있습니다. 다만 세칸을 연속해서 밟을 수는 없습니다. 첫번째 계단만 있는 경우 점수의 최대값은 첫번째 계단을 밟는 것 입니다. 두번째 계단만 있는 경우 점수의 최대값은 첫번째와 두번째 계단을 밟는 것 입니다. 계단의 점수는 자연수이므로, 둘 다 밟는 것이 점수가 무조건 높습니다. 세번째 계단이 있는 경우는 첫번째를 밟고, 세번째를 밟는 경우 두번째를 밟고, ..
[BOJ] 백준 1932 정수 삼각형 (Swift) 문제 https://www.acmicpc.net/problem/1932 1932번: 정수 삼각형 첫째 줄에 삼각형의 크기 n(1 ≤ n ≤ 500)이 주어지고, 둘째 줄부터 n+1번째 줄까지 정수 삼각형이 주어진다. www.acmicpc.net 풀이 왼쪽 대각선 혹은 오른쪽 대각선으로 내려오면서 수들을 더해주고, 가장 큰 수를 구하는 문제입니다. 2차원 배열에 입력을 담아줍시다. 이 테두리에 있는 수들은 위에 수에서 내려올 수 있는 경로가 하나밖에 없습니다. 테두리에 있는 수는 x좌표가 0이거나, y좌표와 x좌표가 같은 경우입니다. x좌표가 0일 때는 (y - 1, x) 에서 내려오는 경로밖에 없습니다. y좌표와 x좌표가 같은 경우일 때는 (y - 1, x - 1) 에서 내려오는 경로밖에 없습니다. 하지..
[BOJ] 백준 1149 RGB거리 (Swift) 문제 https://www.acmicpc.net/problem/1149 1149번: RGB거리 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 www.acmicpc.net 풀이 이 문제의 규칙을 쉽게 설명하면 같은 색으로 연속되게 집을 색칠하지 않고 집을 모두 칠하는 비용의 최소 값을 구해라! 입니다. 1번 집을 빨강으로 칠했다면, 2번 집은 초록과 파랑중에서 골라서 칠해주어야 합니다. 저는 다이나믹 프로그래밍을 떠올렸습니다. 3 * n 크기의 2차원 배열을 사용하였습니다. 초기 값은 처음 집을 칠하는 것이므로, 각각의 칠한 비용으로 설정..
[BOJ] 백준 1912 연속합 (Swift) 문제 https://www.acmicpc.net/problem/1912 1912번: 연속합 첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다. www.acmicpc.net 풀이 연속된 수들을 선택해서 가장 큰 수를 구하는 문제입니다. 그렇다면 이 두가지로 나뉠 것입니다. 연속해서 자기 자신까지 선택한 경우가 더 큰 경우 자기 자신만 선택한 경우 다이나믹 프로그래밍을 사용해서 풀 수 있습니다. [2, 1, -4, 3, 4, -4, 6, 5, -5, 1] 수열이 주어졌을 때를 확인해 봅시다. 첫번째 수를 확인해봅시다. 2를 선택하는 것이 가장 큰 합일 것입니다. 두번째 수를..
[BOJ] 백준 9461 파도반 수열 (Swift) 문제 https://www.acmicpc.net/problem/9461 9461번: 파도반 수열 오른쪽 그림과 같이 삼각형이 나선 모양으로 놓여져 있다. 첫 삼각형은 정삼각형으로 변의 길이는 1이다. 그 다음에는 다음과 같은 과정으로 정삼각형을 계속 추가한다. 나선에서 가장 긴 변의 www.acmicpc.net 풀이 다이나믹 프로그래밍을 사용하여 풀 수 있는 문제입니다. 이 문제는 그림을 보고 점화식을 구했지만.. 증명하지는 못했습니다. 그림을 봤을 때, $f(n) = f(n - 1) + f(n - 5)$ 라는 것을 확인했습니다. 수열을 보면 $f(n) = f(n - 2) + f(n - 3)$도 될 것 같은데... 결론으로는 두 점화식 다 정답 처리가 되더라구요.. 소스코드 후기 규칙을 찾아서 풀긴 했는..
[BOJ] 백준 1904 01타일 (Swift) 문제 https://www.acmicpc.net/problem/1904 1904번: 01타일 지원이에게 2진 수열을 가르쳐 주기 위해, 지원이 아버지는 그에게 타일들을 선물해주셨다. 그리고 이 각각의 타일들은 0 또는 1이 쓰여 있는 낱장의 타일들이다. 어느 날 짓궂은 동주가 지원이 www.acmicpc.net 풀이 다이나믹 프로그래밍으로 풀 수 있는 문제입니다. N이 1일 때는 1만 만들 수 있고, N이 2일 때는 00, 11 로 두 가지를 만들 수 있습니다. N이 3일 때는 어떠할까요? N이 1일 때의 경우에서 "00" 타일 붙히기 + N이 2일때에서 "1"타일을 붙히기 일 것입니다. 따라서 100, 001, 111 로 3가지 경우일 것입니다. 이렇게 이전의 결과들을 바탕으로 다음 결과를 도출할 수 ..
[BOJ] 백준 9184 신나는 함수 실행 (Swift) 문제 https://www.acmicpc.net/problem/9184 9184번: 신나는 함수 실행 입력은 세 정수 a, b, c로 이루어져 있으며, 한 줄에 하나씩 주어진다. 입력의 마지막은 -1 -1 -1로 나타내며, 세 정수가 모두 -1인 경우는 입력의 마지막을 제외하면 없다. www.acmicpc.net 풀이 DP를 사용하여 풀 수 있는 문제입니다. DP는 점화식만 세운다면 쉽게 풀 수 있습니다. 이 문제에서는 점화식을 아예 주고 시작해서, 점화식에 맞게 코드를 작성해줍시다. 먼저, 저는 20 * 20 * 20의 3차원 배열을 선언해주었고, 초기값을 1로 갖고 있도록 하였습니다. 이제 이 3차원 배열을 점화식에 맞게 채워주었습니다. 바텀업 방식으로 풀이할 때는 입력을 받을 때, 0 보다 작거나 ..
반응형

티스토리툴바