본문 바로가기

백준

 (233)
[백준 / BOJ] 1629 곱셈 문제 출처 : www.acmicpc.net/problem/1629 1629번: 곱셈 첫째 줄에 A, B, C가 빈 칸을 사이에 두고 순서대로 주어진다. A, B, C는 모두 2,147,483,647 이하의 자연수이다. www.acmicpc.net a를 b제곱한 수에 c를 나눈 나머지를 구하는 문제다. 풀이 B의 최댓값이 21억이므로 반복문으로 제곱을 해주면 총 21억번 반복을 하게되어서 시간초과가 난다. 분할정복과 수학공식을 이용해서 시간을 최소화해 구해야하는 문제였다. a의 b제곱 = a의 b/2제곱 * a의 b/2제곱 을 사용한다. 단, 지수가 홀수일때는 a의 b제곱 = a의 b/2제곱 * a의 b/2제곱 * a를 해주는것에 유의해야한다. 이해를 돕기위해 위 그림을 보자. 2^8을 계속해서 공식을 사..
[백준 / BOJ] 2410 2의 멱수의 합 문제 출처 : www.acmicpc.net/problem/2410 2410번: 2의 멱수의 합 첫째 줄에 경우의 수를 출력한다. 답이 커질 수 있으므로 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 자연수 N을 입력받았을때, 그 자연수를 2의 멱수의 합으로 나타내는 경우의수를 구하시오 예를들어 3 1 + 1 + 1 1 + 2 두가지 경우로 나타낼수있다. 풀이 www.acmicpc.net/problem/2293 2293번: 동전 1 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. www.acmicpc.net 입력받은 동전들을 ..
[백준 / BOJ] 1261 알고스팟 문제 출처 : www.acmicpc.net/problem/1261 1261번: 알고스팟 첫째 줄에 미로의 크기를 나타내는 가로 크기 M, 세로 크기 N (1 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 미로의 상태를 나타내는 숫자 0과 1이 주어진다. 0은 빈 방을 의미하고, 1은 벽을 의미 www.acmicpc.net N*M크기의 미로가 주어진다. 미로는 0,1로 주어지며 0은 빈 방 1은 벽이다. 알고스팟 운영진이 (1,1)에서 (N,M)으로 이동할때까지 총 몇개의 벽을 부숴야하는지 구하는 문제이다. 풀이 다익스트라를 이용해서 푸는문제다. 벽을 부순 횟수를 저장하는 배열을 만들고 배열의 모든칸을 최댓값으로 초기화 시켜준다. (나는 1000000000로 초기화 해줬음) 위 배열에는 해당 (..
[백준 / BOJ] 13325 이진트리 문제 출처 : www.acmicpc.net/problem/13325 13325번: 이진 트리 문제 각 에지에 양수인 가중치가 부여된 높이가 k인 포화이진트리가 주어져 있다. 높이 k인 포화이진트리는 2k개의 리프를 포함하여 (2k+1 − 1)개의 노드를 가진다. 루트에서 어떤 리프까지의 거�� www.acmicpc.net 1~K높이의 이진트리가 주어졌을때, 한 루트에서 어떤 리프까지의 거리는 루트에서 그 리프까지의 경로상에 있는 모든 에지들의 가중치를 더한 값이다. 각 에지들의 가중치를 증가시켜서 루트에서 모든 리프까지의 거리가 모두 같게하면서 에지의 가중치합을 최소로 만드는 문제다. 풀이 (백준에서 1초에 반복문이 1억번 돈다고 들은것같다..) 최악의 경우인 1^1 + 1^2 + 1 ^ 3 + ... ..
[백준 / BOJ] 6118 숨바꼭질 문제 출처 : www.acmicpc.net/problem/6118 6118번: 숨바꼭질 문제 재서기는 수혀니와 교외 농장에서 숨바꼭질을 하고 있다. 농장에는 헛간이 많이 널려있고 재서기는 그 중에 하나에 숨어야 한다. 헛간의 개수는 N(2
[백준 / BOJ] 1034 램프 문제 출처 : www.acmicpc.net/problem/1034 1034번: 램프 첫째 줄에 N과 M이 주어진다. N은 행의 개수이고, M은 열의 개수이다. N과 M은 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 램프의 상태가 주어진다. 1이 켜져있는 상태이고, 0이 꺼져� www.acmicpc.net N*M배열의 각 칸마다 램프가 들어있고, 한 행이 전부 켜져있을때, 그 행이 켜져있다고 말한다. 램프는 껏다킬수있는데, 한 램프를 선택해서 램프를 키면, 그 램프가 들어있는 행의 모든 열이 다 켜진다. N*M배열의 크기와 각 칸에 들어있는 램프의 상태가 주어졌을때, K번 램프를 껏다킨후 켜져있는 행의 최댓값을 구하는 문제다. 풀이 완전탐색으로 접근하면 시간초과가 날거같아서 ((1000 *..
[백준 / BOJ] 5052 전화번호 목록 문제 출처 : www.acmicpc.net/problem/5052 5052번: 전화번호 목록 문제 전화번호 목록이 주어진다. 이때, 이 목록이 일관성이 있는지 없는지를 구하는 프로그램을 작성하시오. 전화번호 목록이 일관성을 유지하려면, 한 번호가 다른 번호의 접두어인 경우가 없� www.acmicpc.net 전화번호 목록을 입력받았을때, 그 목록이 일관성이 있나 없나 구하는 문제다. 예를들어 A = 911 B = 9123 C = 91 1234 를 입력받았을때, C에게 전화할려고 전화번호를 누르면 911을 누르는순간 A에게 전화가 가므로 일관성이없는 목록이다. 풀이 Trie알고리즘을 배우고 풀었는데, 새로운 알고리즘이라기 보다 구조체를 응용하는 느낌이였다. 구조체를 선언하고 그 구조체에 자판 배열을 할당한..
[백준 / BOJ] 1241 머리 톡톡 문제 출처 : www.acmicpc.net/problem/1241 1241번: 머리 톡톡 엄지 생일 기념으로 학생들은 파티를 하고 있다. 엄지는 N(1≤N≤100,000)명의 학생에게 1부터 N번까지 차례대로 번호를 부여하였고 그들을 순서대로 빙 둘러앉아 원을 만들게 하였다. (즉 i번째 학� www.acmicpc.net N명의 학생이 원형으로 앉아있다. 1번 학생부터 N번 학생까지 순서대로 일어나면서 자신이 쓴 숫자가 다른사람의 숫자의 배수라면 머리를 한대친다. 이때 각학생이 머리를 총 몇번치는지 구하는 문제이다. 풀이 완전탐색으로 풀게되면 100001 * 50000이라 시간초과가 난다. arr배열을 만들어 해당 숫자가 나온 횟수를 저장해주고, 약수가 되는 값의 범위를 찾아 풀었다. i번 학생이 머리에..

티스토리툴바