목록백준 (183)
Study hard
https://www.acmicpc.net/problem/1451 1451번: 직사각형으로 나누기 첫째 줄에 직사각형의 세로 크기 N과 가로 크기 M이 주어진다. 둘째 줄부터 직사각형에 들어가는 수가 가장 윗 줄부터 한 줄에 하나씩 M개의 수가 주어진다. N과 M은 100보다 작거나 같은 자연수이� www.acmicpc.net [풀이] 직사각형을 세 개의 직사각형으로 나누는 경우는 아래와 같이 6가지가 있다 세 개의 직사각형은 모두 같은 크기일 필요가 없으므로 위의 모양들 각각으로 자르는 경우 안에서도 가능한 모든 경우의 수를 찾아봐야 한다. #include #include //max #include //scanf using namespace std; int N, M; int Num[101][101]; ..
https://www.acmicpc.net/problem/1107 1107번: 리모컨 첫째 줄에 수빈이가 이동하려고 하는 채널 N (0 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 고장난 버튼의 개수 M (0 ≤ M ≤ 10)이 주어진다. 고장난 버튼이 있는 경우에는 셋째 줄에는 고장난 버튼�� www.acmicpc.net [풀이] brute force로 풀었다. 1. 0~INF 모든 수 중 고장난 버튼을 누르지 않아도 되고, 이동하려고 하는 채널과 가장 가까운 수를 찾기 2. 1)에서 찾은 수의 길이+이동하려고 하는 채널과의 차이와 현재 채널인 100과 이동하려고 하는 채널의 차이를 비교했을 때 더 작은 수를 출력 누를 수 있는 수인지 확인할 때 0인 경우를 따로 처리해 줘야 한다. ∵ whil..
https://www.acmicpc.net/problem/1476 1476번: 날짜 계산 준규가 사는 나라는 우리가 사용하는 연도와 다른 방식을 이용한다. 준규가 사는 나라에서는 수 3개를 이용해서 연도를 나타낸다. 각각의 수는 지구, 태양, 그리고 달을 나타낸다. 지구를 나타�� www.acmicpc.net [풀이] 1 1 1 : 1 1 16 16 : 16 1 2 3 : 5266 15 28 19 : 7980 위 예제들을 보면, year - E = 15의 배수, year - S = 28의 배수, year - M = 19의 배수인 공통된 year을 찾는 문제라는 것을 알 수 있다. #include using namespace std; int E, S, M; void getYear() { int year =..
https://www.acmicpc.net/problem/1517 1517번: 버블 소트 첫째 줄에 N(1≤N≤500,000)이 주어진다. 다음 줄에는 N개의 정수로 A[1], A[2], …, A[N]이 주어진다. 각각의 A[i]는 0≤|A[i]|≤1,000,000,000의 범위에 들어있다. www.acmicpc.net [풀이] 버블소트 문제지만 버블소트로 풀면 시간초과가 나온다. (시간복잡도O(n^2)) 그래서 시간복잡도가 O(nlogn)인 mergesort를 사용하여 풀었다. 버블 소트 swap은 인접해 있는 두 수를 바꾸는 것이므로, merge를 할 때 두 수의 앞뒤 순서가 바뀌면 두 수의 거리를 카운트하는 변수에 더하면 된다. #include #include using namespace std; ..
https://www.acmicpc.net/problem/2448 2448번: 별 찍기 - 11 첫째 줄에 N이 주어진다. N은 항상 3×2k 수이다. (3, 6, 12, 24, 48, ...) (k ≤ 10) www.acmicpc.net [풀이] 분할 정복을 사용하여 풀어야 한다. 배열 star[N][2 * N - 1] 별을 저장한 다음 재귀함수에서 벗어나면 출력하는 방식으로 했다. 아래와 같이 N이 가장 작은 수인 3일 때의 형태가 기본단위가 된다. 즉, N이 3이 될때까지 재귀를 돌리고, N이 3이 되면 기본단위를 그려주면 된다. 위 형태를 보면 제일 위의 꼭지점 좌표가 (x,y)라고 할 때(x=0, y=N-1), 각 기본단위의 꼭지점의 위치가 (x,y), (x + N/2, y - N/2), (x ..
https://www.acmicpc.net/problem/2447 2447번: 별 찍기 - 10 재귀적인 패턴으로 별을 찍어 보자. N이 3의 거듭제곱(3, 9, 27, ...)이라고 할 때, 크기 N의 패턴은 N×N 정사각형 모양이다. 크기 3의 패턴은 가운데에 공백이 있고, 가운데를 제외한 모든 칸에 별이 � www.acmicpc.net [풀이] 분할 정복을 이용한 별 찍기 문제였다. 가장 작은 단위는 N이 3일 때 이고, 빈칸의 좌표는 (1,1)이다. 기본 단위가 여러개 붙어있으면 이와 같은 모양이고, 빈칸의 좌표는 (1,1), (1,4), (1,7), (1,10), (1,13), (1,16), (1,19), (1,22), (1,25)이다. 즉, x%3=1이고, y%3=1인 좌표에서 빈칸이 나와야 ..