본문 바로가기

수학

 (20)
[백준 / BOJ] 16967 배열 복원하기 문제 출처 : https://www.acmicpc.net/problem/16967 16967번: 배열 복원하기 크기가 H × W인 배열 A와 두 정수 X와 Y가 있을 때, 크기가 (H + X) × (W + Y)인 배열 B는 배열 A와 배열 A를 아래로 X칸, 오른쪽으로 Y칸 이동시킨 배열을 겹쳐 만들 수 있다. 수가 겹쳐지면 수가 합쳐 www.acmicpc.net 크기가 H*W인 배열A를 아래로 X 오른쪽으로 Y만큼 이동한 배열을 배열 A와 겹쳤을때 나온 배열을 배열 B라고 하자. (배열이 겹쳐지면 같은 위치의 수가 합쳐진다.) 배열의 크기 H, W 이동범위 X, Y, 배열 B가 주어질때 배열 A를 구하는 문제다. 풀이 수학? 구현? 문제다. 배열B가 주어졌을때, 원래 배열의 (i,j)의 값은 다음과 같..
[백준 / BOJ] 1033 칵테일 (Java) 문제 출처 : https://www.acmicpc.net/problem/1033 1033번: 칵테일 august14는 세상에서 가장 맛있는 칵테일이다. 이 칵테일을 만드는 정확한 방법은 아직 세상에 공개되지 않았지만, 들어가는 재료 N개는 공개되어 있다. 경근이는 인터넷 검색을 통해서 재료 쌍 N www.acmicpc.net august14는 세상에서 가장 맛있는 칵테일이다. 이 칵테일을 제조하기위한 재료의 갯수 N과 각 재료의 비율이 주어졌을때, 칵테일을 만들기위해 필요한 재료의 질량을 출력하는 문제다. 풀이 유클리드 호제법을 응용해서 푸는 수학 문제였다. 문제에서 두가지 재료의 비율이 주어진다. 이 비율을 갖고 각 재료의 질량을 구하는 공식을 만들어보면, 재료를 각각 a,b 비율을 p,q라 했을때, ..
[백준 / BOJ] 9881 Ski Course Design (Java) 문제 출처 : https://www.acmicpc.net/problem/9881 9881번: Ski Course Design Farmer John has N hills on his farm (1
[백준 / BOJ] 1242 소풍 (Java) 문제 출처 : https://www.acmicpc.net/problem/1242 1242번: 소풍 첫째 줄에 N, K, M가 주어진다. N과 K는 5,000,000보다 작거나 같은 자연수이고, M은 N보다 작거나 같다. www.acmicpc.net 소풍을간 사람의 수 N 제거될 사람의 번호 K 동호의 번호 M 이 주어진다. 사람들이 원형으로 둘러앉아 순서대로 번호를 외칠때, K를 외친사람이 탈락하고, 이후 남은사람들끼리 다시 게임을 시작한다. 동호는 자신이 몇번째에 탈락할지 궁금하다. 동호가 몇번째에 탈락하는지 구하는 프로그램을 만들자. 풀이 어려웠던 문제다. 처음에는 현재 제거될 사람의 위치를 구하기위해 유니온파인드를 사용해서 경로를 압축해줄려했다. 예를들어, 1 2 3 4 5에서 2번, 3번이 이미 ..
[백준 / BOJ] 1747 소수 & 팰린드롬 문제 출처 : https://www.acmicpc.net/problem/1747 1747번: 소수&팰린드롬 어떤 수와 그 수의 숫자 순서를 뒤집은 수가 일치하는 수를 팰린드롬이라 부른다. 예를 들어 79,197과 324,423 등이 팰린드롬 수이다. 어떤 수 N (1 ≤ N ≤ 1,000,000)이 주어졌을 때, N보다 크거나 같고, www.acmicpc.net 숫자 N이 주어졌을때, N보다 크거나 같은수중 소수이면서 팰린드롬인 수중 가장 작은 수를 찾는문제다. 풀이 에라토스테네스의 채를 이용해 풀은문제다. 우선, 에라토스테네스의 채의 최대 범위를 지정해주기위해, N = 1,000,000일때, 소수이면서 팰린드롬인 수중 가장 작은수를 찾아보면, 1003001 이라는것을 알수있다. 따라서, 소수를 걸러주기..
[백준 / BOJ] 1256 사전 문제 출처 : www.acmicpc.net/problem/1256 1256번: 사전 첫째 줄에 N, M, K가 순서대로 주어진다. N과 M은 100보다 작거나 같은 자연수이고, K는 1,000,000,000보다 작거나 같은 자연수이다. www.acmicpc.net "a","z"로만 이루어진 문자열이 수록된 사전이있다. 사전에 있는 문자열은 모두 알파벳 순서로 정렬되어있다. "a"의 갯수 N, "z"의 갯수 M이 주어질때, K번째 문자열이 무엇인지 찾는 문제다. 풀이 수학 문제였다. N과 M이 각각 100까지 갈수있기때문에. 완전탐색으로 모든 가지를 만들며 풀경우 약 10^60번 반복하며 시간안에 절대 풀지못한다. 조합을 이용해 찾고자하는 칸 만큼 건너뛰면서 K번째 문자열을 찾아야했다. 아이디어는 다음과 ..
[백준 / BOJ] 10830 행렬 제곱 문제 출처 : www.acmicpc.net/problem/10830 10830번: 행렬 제곱 크기가 N*N인 행렬 A가 주어진다. 이때, A의 B제곱을 구하는 프로그램을 작성하시오. 수가 매우 커질 수 있으니, A^B의 각 원소를 1,000으로 나눈 나머지를 출력한다. www.acmicpc.net 크기가 N*N인 행렬A가 주어졌을때, 해당 행렬을 B제곱한 결과를 구하는 문제다. 수가 매우 커질수있으니 A^B의 각 원소를 1000으로 나눈 나머지를 출력한다. 풀이 B가 최대 100,000,000,000까지 가서 일반적인 곱셈(A*A*A*A*A)으로는 시간초과가 난다. 분할정복을 이용해 풀어야하는데, A*A = A^2 A*A*A*A = A^2*A^2 = A^4 A*A*A*A*A*A*A*A = A^2*A^2..
[백준 / BOJ] 17087 숨바꼭질 6 문제 출처 : www.acmicpc.net/problem/17087 17087번: 숨바꼭질 6 수빈이는 동생 N명과 숨바꼭질을 하고 있다. 수빈이는 현재 점 S에 있고, 동생은 A1, A2, ..., AN에 있다. 수빈이는 걸어서 이동을 할 수 있다. 수빈이의 위치가 X일때 걷는다면 1초 후에 X+D나 X-D로 이 www.acmicpc.net 수빈이가 동생'들'과 숨바꼭질을한다. 선영이는 +D, -D만큼 이동할수있다. 선영이의 위치와 동생들의 위치가 주어졌을때, 선영이가 모든 동생을 찾을수있는 최대 D값을 찾는문제다. 풀이 수학문제다. 선영이는 모든 동생을 찾아야한다. 선영이는 항상 +D, -D만큼 움직일수있으므로, 모든 동생과의 거리차들의 최대공약수만큼 움직여야 모든동생들을 찾을수있다. 1. 선영이의 ..

티스토리툴바