본문 바로가기
728x90

전체 글205

[BOJ/백준] 9095 1, 2, 3 더하기 ● [문제번호 9095] 1, 2, 3 더하기 https://www.acmicpc.net/problem/9095 9095번: 1, 2, 3 더하기 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다. www.acmicpc.net ● 알아야 할 것 : DP 문제집에 있는 문제 https://pirateturtle.tistory.com/202 ● 풀이 과정 : DP의 풀이과정 (Bottom - Up) 1. 테이블 정의하기 → 각 index의 값은 1, 2, 3의 합으로 나타내는 방법의 수를 나타낸다. 2. 점화식 찾기 → dp[index] = dp[index - 1] + dp[index - 2] + dp[index - 3] dp[index]는 dp[index - 1] 에서 구한.. 2021. 9. 2.
[BOJ/백준] 1748 수 이어 쓰기 1 ● [문제번호 1748] 수 이어 쓰기 1 https://www.acmicpc.net/problem/1748 1748번: 수 이어 쓰기 1 첫째 줄에 N(1 ≤ N ≤ 100,000,000)이 주어진다. www.acmicpc.net ● 알아야 할 것 : 브루트 포스 (Brute Force) : 숫자 → 문자 변환 방법 : {math헤더 - pow(a, b)} a의 b제곱 ● 풀이 과정 : string 문자열을 이용하여 간단하게 구현하면 '메모리 초과' 결과가 나온다. 조금 더 고민하니 약간의 규칙이 있어서 수학적 계산만 하면 된다. : 입력된 숫자의 자릿수가 len이라고 할 때 len - 1까지 (9 * i * 10^i) 로 구할 수 있다. (단, i < len) 그 다음 len 자릿수들의 길이만큼 더하.. 2021. 9. 2.
[BOJ/백준] 6064 카잉 달력 ● [문제번호 6064] 카잉 달력 https://www.acmicpc.net/problem/6064 6064번: 카잉 달력 입력 데이터는 표준 입력을 사용한다. 입력은 T개의 테스트 데이터로 구성된다. 입력의 첫 번째 줄에는 입력 데이터의 수를 나타내는 정수 T가 주어진다. 각 테스트 데이터는 한 줄로 구성된다. www.acmicpc.net ● 알아야 할 것 : 브루트 포스 (Brute Force) : 최대공약수, 최소공배수 (유클리드 호제법) ● 풀이 과정 : 이전에 있던 [1476 날짜계산] 과 비슷한 문제다. 대신 최소공배수와 시간복잡도를 줄이기 위한 고려 사항이 추가되었다. 시간복잡도를 줄이는 방법이 마땅히 떠오르지 않아 구글링하였다. : 각 테스트케이스의 마지막 해는 M, N의 최소공배수 이다.. 2021. 9. 2.
[BOJ/백준] 14500 테트로미노 ● [문제번호 14500] 테트로미노 https://www.acmicpc.net/problem/14500 14500번: 테트로미노 폴리오미노란 크기가 1×1인 정사각형을 여러 개 이어서 붙인 도형이며, 다음과 같은 조건을 만족해야 한다. 정사각형은 서로 겹치면 안 된다. 도형은 모두 연결되어 있어야 한다. 정사각형의 변 www.acmicpc.net ● 알아야 할 것 : 브루트 포스 (Brute Force) ● 풀이 과정 : 풀이 과정이나 떠올리기 어려워서 구글링을 했다. BFS 방법 + 'ㅗ' 형태 예외 처리를 하는 코드가 꽤 있었지만, 브루트 포스에 맞게 하드코딩했다. : 각 형태에 마다 나올 수 있는 모습을 고려한다. (총 19가지) 각 형태마다 범위를 벗어나는 경우가 없게 조심하며, 빠짐없이 구현한.. 2021. 9. 2.
[BOJ/백준] 1107 리모컨 ● [문제번호 1107] 리모컨 https://www.acmicpc.net/problem/1107 1107번: 리모컨 첫째 줄에 수빈이가 이동하려고 하는 채널 N (0 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 고장난 버튼의 개수 M (0 ≤ M ≤ 10)이 주어진다. 고장난 버튼이 있는 경우에는 셋째 줄에는 고장난 버튼 www.acmicpc.net ● 알아야 할 것 : 브루트 포스 (Brute Force) ● 풀이 과정 : 목표 채널로 이동하는 방법 1. +, - 로만 이동하는 경우 → 목표 채널 - 현재 채널(100) 2. 숫자 버튼을 이용해 채널 이동 후 +, - 로 이동하는 경우 어떤 채널로 이동해야 할까 → (고장나지 않은 숫자 버튼으로 갈 수 있는) (목표 채널과 가장 가까운) 채널 .. 2021. 9. 2.
[BOJ/백준] 1476 날짜 계산 ● [문제번호 1476] 날짜 계산 https://www.acmicpc.net/problem/1476 1476번: 날짜 계산 준규가 사는 나라는 우리가 사용하는 연도와 다른 방식을 이용한다. 준규가 사는 나라에서는 수 3개를 이용해서 연도를 나타낸다. 각각의 수는 지구, 태양, 그리고 달을 나타낸다. 지구를 나타 www.acmicpc.net ● 알아야 할 것 : 브루트 포스 (Brute Force) ● 풀이 과정 : 간단하게 나머지 연산을 이용하여 하나씩 모두 검사하면 된다. ● 주의 할 것 : 나머지 연산한 값이 0인 경우 연도로 바꾸려면 나누는 값(15, 28, 19)이 된다. 예를 들어 1 % 15 → 1 2 % 15 → 2 ... 14 % 15 → 14 15 % 15 → 0 마지막 경우는 15로 .. 2021. 9. 2.
728x90