본문 바로가기
  • 개발 삽질 블로그

프로그래밍46

백준 9095번: 1, 2, 3 더하기 https://www.acmicpc.net/problem/9095 9095번: 1, 2, 3 더하기 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다. www.acmicpc.net 이 문제는 조금 어려웠던 것 같다. 알고리즘 분류는 다이나믹 프로그래밍이다. 다이나믹 프로그래밍이란 특정 범위까지의 값을 구하기 위해서 그것과 다른 범위까지의 값을 이용하여 효율적으로 값을 구하는 알고리즘 설계 기법이다. 1 = 1 (1개) 2 = 1 + 1 = 2 (2개) 3 = 1 + 1 + 1 = 1 + 2 = 2 + 1 = 3 (4개) 4 = 1 + 1 + 1 + 1 = 1 + 1 + 2 = 1 + 2 + 1 = 2 + 1 + 1 = 2 + 2 = 1 + 3 = 3 + 1(7개) n을 1.. 2022. 10. 3.
백준 1748: 수 이어 쓰기 1 https://www.acmicpc.net/problem/1748 1748번: 수 이어 쓰기 1 첫째 줄에 N(1 ≤ N ≤ 100,000,000)이 주어진다. www.acmicpc.net 이 문제는 노트에 좀 써보면 알고리즘을 찾기 쉬웠던 것 같다. N을 입력 받고 N의 자릿수를 구해준다. N의 자릿수를 l이라고 두고 풀었다. N까지 한 자리 수: 9개 //1~9 두 자리 수: 90개 //10~99 세 자리 수: 900개 //100~999 ... l-1자리 수 : 9*(10^(l-2))개 //100...0~999..9 그리고 l 자리수는 N-(10^(l-1))+1개 있다. import java.util.*; public class Main { public static void main(String[] .. 2022. 10. 3.
백준 2309: 일곱 난쟁이[JAVA] / 투포인터 https://www.acmicpc.net/problem/2309 2309번: 일곱 난쟁이 아홉 개의 줄에 걸쳐 난쟁이들의 키가 주어진다. 주어지는 키는 100을 넘지 않는 자연수이며, 아홉 난쟁이의 키는 모두 다르며, 가능한 정답이 여러 가지인 경우에는 아무거나 출력한다. www.acmicpc.net 9명 중 7명을 뽑는 것은 포함하지 않은 2명을 뽑는 것과 같다. 9명 난쟁이들의 키의 합을 구하고 100과의 차이를 구한다. 그 차이를 n이라고 두면 n은 일곱 난쟁이에 포함되지 않는 두 명의 키의 합과 같을 것이다. 반복문을 돌려 키의 합이 n인 난쟁이 두 명을 찾아주는 알고리즘을 짰다. import java.util.*; public class Main { public static void main(.. 2022. 10. 3.
C로 푼 문제들 보호되어 있는 글 입니다. 2022. 9. 7.
백준 1978: 소수찾기(JAVA) https://www.acmicpc.net/problem/1978 1978번: 소수 찾기 첫 줄에 수의 개수 N이 주어진다. N은 100이하이다. 다음으로 N개의 수가 주어지는데 수는 1,000 이하의 자연수이다. www.acmicpc.net 이전 소수 관련 문제 풀이와 비슷하다. 1000이하의 자연수에 대해 판별하는 것이기 때문에 1부터 1000까지 소수인지 아닌지를 미리 구해주고 prime이라는 boolean 배열에 담아준다. 2부터 1000까지 배수인 것을 소수가 아니라고 표시한다. 아래 코드에서는 prime[i]가 false이면 i는 소수이다. import java.util.*; public class Main { public static void main(String[] args){ Scanne.. 2022. 8. 20.
백준 17425: 약수의 합(JAVA) https://www.acmicpc.net/problem/17425 17425번: 약수의 합 두 자연수 A와 B가 있을 때, A = BC를 만족하는 자연수 C를 A의 약수라고 한다. 예를 들어, 2의 약수는 1, 2가 있고, 24의 약수는 1, 2, 3, 4, 6, 8, 12, 24가 있다. 자연수 A의 약수의 합은 A의 모든 약수를 더 www.acmicpc.net 이 문제는 이전 문제의 심화버전인 것 같다. 이전 약수의 합 문제 + 여러 개의 테스트 케이스 이전 17427번 문제를 풀었던 코드를 응용했다. n이 1부터 1000000까지 f(n)과 g(n)을 구한다. 여기서 g(n) = g(n-1) + f(n)이라는 것을 알면 코드를 쉽게 짤 수 있다. T번 만큼 N을 입력받아 각 g(N) 값을 출력해주.. 2022. 8. 18.

티스토리툴바