본문 바로가기

문제 해결/BOJ117

[백준] 팩토리얼 0의 개수 https://www.acmicpc.net/problem/11687 11687번: 팩토리얼 0의 개수 첫째 줄에 M (1 ≤ M ≤ 100,000,000)이 주어진다. www.acmicpc.net 1. 문제 이해 0의 개수가 m개가 되는 n!의 n을 찾는 문제 2. 문제 접근 5의 개수가 m개가 되는 팩토리얼을 찾아주면 되는 문제입니다. 그래서 처음에는 5의 배수 숫자들을 찾으면 5로 계속 나눠주면서 몇개의 5가 포함되어있는지를 찾았습니다. 하지만 이렇게 풀이를 하게 되면 시간 초과가 나게 됩니다. 중요한 포인트는 N보다 작은 수들 중에서 5로 나눠지는 숫자의 개수를 찾는 것입니다. 이를 찾는 가장 쉬운 방법은 5로 나눠보면 알 수 있습니다. ex) 41 -> 41 // 5 = 8(5, 10, 15, 2.. 2023. 11. 7.
[백준] 연산자 끼워넣기 (2) 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 1. 문제 이해 N개의 수로 이루어진 수열의 숫자 사이사이에 연산자를 끼워넣어서 최소, 최대값을 구하는 문제 2. 문제 접근 N이 최대 11까지 가능하고 연산자의 개수는 40까지 가능하므로 대략 40P4라고 생각해보아도 시간초과가 나지 않기 때문에 조합을 활용하여 풀이 3. 풀이 import sys MAX = 1000000001 sys.s.. 2023. 11. 1.
[백준] 부분 삼각 수열 https://www.acmicpc.net/problem/1548 1548번: 부분 삼각 수열 세 수 x, y, z가 x+y>z, x+z>y, y+z>x의 관계를 만족하면, 세 수는 삼각관계에 있다고 한다. 마찬가지로 길이가 N인 수열 B(b[0], b[1], ..., b[n-1])의 모든 b[i], b[j], b[k]가 삼각관계에 있으면 이 수열은 삼각 www.acmicpc.net 1. 문제 이해 수열이 주어지고 수열에 포함된 숫자 중 3개를 뽑았을 때 x+y>z, x+z>y, y+z>x를 만족하는 가장 긴 수열을 찾는 문제입니다. 단, 숫자를 원하는대로 삭제할 수 있습니다. 2. 문제 접근 수열을 선택했을 때, 가장 작은 두 숫자의 합이 수열에서 가장 큰 수보다 커야합니다. 따라서, 수열을 정렬하고 .. 2023. 9. 21.
[백준] 연속합 2 https://www.acmicpc.net/problem/13398 13398번: 연속합 2 첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다. www.acmicpc.net 1. 문제이해 수열에서 연속된 수를 선택해서 얻을 수 있는 가장 큰 합을 구하는 문제입니다. 무조건 하나의 수는 선택해야하고 하나의 숫자를 제거한 다음 연속된 수를 선택할 수 있습니다. 2. 문제접근 DP 방식으로 접근해 보았습니다. dp[0][i]: 숫자를 삭제하지 않은 경우 dp[1][i]: 숫자를 한개 삭제한 경우로 나누어서 풀이하면 됩니다. 점화식은 다음과 같습니다. dp[0][i] = max.. 2023. 9. 9.
[백준] 창업 문제 링크: https://www.acmicpc.net/problem/16890 16890번: 창업 입력은 길이가 N(1 ≤ N ≤ 300,000)인 문자열 두 개로 이루어져 있다. 모든 문자열은 알파벳 소문자로만 이루어져 있다. 첫 번째 줄에 주어지는 문자열은 구사과가 고른 문자이고, 두 번째 줄에 주 www.acmicpc.net 1. 문제 이해 구사과와 큐브러버가 사명을 정하는데 구사과는 사전순으로 가장 앞서게 하고 싶고 큐브러버는 사전 순으로 늦게 나오도록 하고 싶다. 각자 고른 알파벳 문자 N개가 있고 구사과를 시작으로 하나씩 문자를 배치할 수 있다. 최종적으로 N개의 알파벳을 배치하여 나온 사명을 알아내는 것이 문제의 목표입니다. 2. 문제 접근 deque를 활용하는 게임 이론인 것까지는 접근했.. 2023. 6. 18.
[백준] 돌다리 건너기 https://www.acmicpc.net/problem/2602 2602번: 돌다리 건너기 첫째 줄에는 마법의 두루마리에 적힌 문자열(R, I, N, G, S 로만 구성된)이 주어진다. 이 문자열의 길이는 최소 1, 최대 20 이다. 그 다음 줄에는 각각 와 를 나타내는 www.acmicpc.net 1. 문제이해 마법의 두루마리에 적혀있는 단어의 문자순서대로 악마의 돌다리와 천사의 돌다리를 번갈아가면서 밟을 수 있는 모든 경우의 수를 구하는 문제입니다. 2. 문제접근 접근 방식: DP 제일 못하는 재귀 DP입니다. DP[k][i][j]라고 정의했을때 k = 0인 경우는 천사의 돌다리를 건널 차례일 때 마법의 두루마리의 i번째 문자를 돌다리에서 j인덱스부터 찾는 경우를 의미합니다. 재귀를 돌면서 돌다리를.. 2023. 5. 11.
[백준] 스위치 https://www.acmicpc.net/problem/1395 1395번: 스위치 첫 줄에는 스위치의 개수 N(2 ≤ N ≤ 100,000)과 처리할 일의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 다음 M개의 줄에 대해 각 줄에 처리할 일에 대한 정보가 담겨진 세 개의 정수 O, Si, Ti가 입력된다. O www.acmicpc.net 1. 문제 이해 N개의 스위치가 주어지고 두가지 연산이 주어집니다. A번부터 B번 사이의 스위치 상태를 반전시키는 것이고 다른 하나는 C번부터 D번 사이의 스위치 중 켜져있는 스위치의 개수를 세는 것입니다. 2. 문제 접근 레이지 프로퍼게이션을 활용한 세그멘트 트리를 활용하는 문제입니다. lazy배열에는 현재 범위에 있는 스위치들을 반전시키는 작업이 필요한지.. 2023. 5. 3.
[백준] 배열 돌리기 4 https://www.acmicpc.net/problem/17406 17406번: 배열 돌리기 4 크기가 N×M 크기인 배열 A가 있을때, 배열 A의 값은 각 행에 있는 모든 수의 합 중 최솟값을 의미한다. 배열 A가 아래와 같은 경우 1행의 합은 6, 2행의 합은 4, 3행의 합은 15이다. 따라서, 배열 A의 www.acmicpc.net 1. 문제 이해 (r, c)를 중심으로 가장 왼쪽 위가 (r - s, c - s)이고 오른쪽 아래가 (r + s, c + s)가 왼쪽 아래인 정사각형을 돌리는 회전연산이 주어집니다. 임의의 순서로 K개의 회전연산을 수행했을 때 행의 합이 최소를 구하는 문제입니다. 2. 문제 접근 deque를 이용한 구현으로 풀이하였습니다. permutation을 통해서 회전연산의 순.. 2023. 5. 2.
[백준] 소용돌이 예쁘게 출력하기 https://www.acmicpc.net/problem/1022 1022번: 소용돌이 예쁘게 출력하기 첫째 줄에 네 정수 r1, c1, r2, c2가 주어진다. www.acmicpc.net 1. 문제 이해 1이 위치하는 좌표를 (0, 0)이라고 했을 때 밑 사진과 같이 반시계로 소용돌이 모양으로 숫자를 채워나갈 때 (r1,c1) ~ (r2, c2)까지 범위의 숫자들을 '예쁘게' 출력하면 됩니다. 2. 문제 접근 1을 시작으로 오른쪽 아래의 숫자들의 증가폭이 8, 16, 24가 됨을 알 수 있었습니다. 이를 활용하여 사각형의 테두리에서 가장 큰 숫자를 얻을 수 있습니다. 그리고 각 숫자들은 행과 열의 값 중 절대값이 더 큰 값을 n이라고 했을 때 n + 1번째 사각형에 속하게 됩니다. 예를 들어 34는 .. 2023. 5. 1.

티스토리툴바