목록백준/etc (36)
mojo's Blog
[백준 5052] 전화번호 목록
문제 링크 => 5052번: 전화번호 목록 (acmicpc.net) 5052번: 전화번호 목록 첫째 줄에 테스트 케이스의 개수 t가 주어진다. (1 ≤ t ≤ 50) 각 테스트 케이스의 첫째 줄에는 전화번호의 수 n이 주어진다. (1 ≤ n ≤ 10000) 다음 n개의 줄에는 목록에 포함되어 있는 전화번호가 www.acmicpc.net Trie 자료구조를 이용한 문제이다. 사실 Sorting 을 이용하면 난이도가 급격하게 낮아지지만 삼성 하계 sw 때 배웠던 자료구조 Trie 를 이용해서 풀었다. 문제 자체의 흐름은 파악했으나 실수한 점이 있다. Input을 하나하나 읽은 동시에 바로 check 했다는 점에 있다. 예시를 들어보자. 12345, 123 순으로 들어왔다고 가정한다면 (1) 12345 => ..
[백준 9527] 1의 개수 세기
문제 링크 => 9527번: 1의 개수 세기 (acmicpc.net) 9527번: 1의 개수 세기 두 자연수 A, B가 주어졌을 때, A ≤ x ≤ B를 만족하는 모든 x에 대해 x를 이진수로 표현했을 때 1의 개수의 합을 구하는 프로그램을 작성하시오. 즉, f(x) = x를 이진수로 표현 했을 때 1의 개수라 www.acmicpc.net 수학을 이용한 문제이다. 먼저 규칙성을 발견하면 다음과 같다. (1) 2^0 ~ 2^1 - 1 일 때 1의 개수의 합 : 1 = 1 + 0 (2) 2^1 ~ 2^2 - 1 일 때 1의 개수의 합 : 3 = 2 + 1 (3) 2^2 ~ 2^3 - 1 일 때 1의 개수의 합 : 8 = 4 + 4 (4) 2^3 ~ 2^4 - 1 일 때 1의 개수의 합 : 20 = 8 + 1..
[백준 10986] 나머지 합
문제 링크 => 10986번: 나머지 합 (acmicpc.net) 10986번: 나머지 합 수 N개 A1, A2, ..., AN이 주어진다. 이때, 연속된 부분 구간의 합이 M으로 나누어 떨어지는 구간의 개수를 구하는 프로그램을 작성하시오. 즉, Ai + ... + Aj (i ≤ j) 의 합이 M으로 나누어 떨어지는 (i, j) www.acmicpc.net 누적합을 이용한 문제이다. i 번째에서 j 번째까지 원소들의 합이 M으로 나누어 떨어지는 모든 경우를 구해야 한다. 이해하기 쉽도록 예시를 들어보도록 하자. ex ) 원소 5개 [1, 2, 3, 4, 5] 이 있고 3 으로 나누어 떨어지는 모든 경우의 수를 구하시오. 1. 배열 A에 대한 정보는 다음과 같다. 1 2 3 4 5 2. sum[i] = (..
[백준 2829] 아름다운 행렬
문제 링크 => 2829번: 아름다운 행렬 (acmicpc.net) 2829번: 아름다운 행렬 첫째 줄에 행렬의 크기 N이 주어진다. (2 ≤ N ≤ 400) 다음 N개의 줄에는 행렬의 성분이 공백으로 구분되어 주어진다. 각 성분은 [-1000,1000] 범위 안에 들어있다. www.acmicpc.net Brute Force 문제이다. 부 대각선에 대한 합들을 미리 구하여 모든 주 대각선을 탐색하면서 미리 구한 값들을 빼는 방식으로 접근했다. Solution Code #define _CRT_SECURE_NO_WARNINGS #include #include #include #include #include #include #include #include #include #include #define endl..
[백준 5904] Moo 게임
문제 링크 => 5904번: Moo 게임 (acmicpc.net) 5904번: Moo 게임 Moo는 술자리에서 즐겁게 할 수 있는 게임이다. 이 게임은 Moo수열을 각 사람이 하나씩 순서대로 외치면 되는 게임이다. Moo 수열은 길이가 무한대이며, 다음과 같이 생겼다. m o o m o o o m o o m o o o www.acmicpc.net 재귀를 이용한 분할 정복문제이다. 이 문제는 다음과 같이 Moo 수열을 만들 수 있다. S(0) = moo S(1) = moo mooo moo S(2) = moo mooo moo moooo moo mooo moo ... S(k) = S(k - 1) moo ... o S(k - 1) (o의 개수는 (k + 2) 개) 이런식으로 Moo 수열을 구할 수 있다. 근데 ..
[백준 1515] 수 이어 쓰기
문제 링크 => 1515번: 수 이어 쓰기 (acmicpc.net) 1515번: 수 이어 쓰기 세준이는 1부터 N까지 모든 수를 차례대로 공백없이 한 줄에 다 썼다. 그리고 나서, 세준이가 저녁을 먹으러 나간 사이에 다솜이는 세준이가 쓴 수에서 마음에 드는 몇 개의 숫자를 지웠다. 세준 www.acmicpc.net 문자열을 이용한 구현 문제이다. 먼저 정해진 것은 아니지만 [1, 99999] 범위 내의 모든 숫자을 이어주도록 하는 문자열 s를 설정하였다. 그리고 123456789101112... 이런식으로 나아갈 때 [x, y] 범위 내의 숫자를 z 라고 설정하기 위해 1차원 배열 dp를 둬서 dp[x] = dp[x + 1] = ... = dp[y - 1] = dp[y] = z 이런 식으로 설정하였다. ..