[백준/C++] 1699번 - 제곱수의 합

오늘의 문제! https://www.acmicpc.net/problem/1699 입력 첫째 줄에 N이 주어짐 풀이 1로만 구성된 경우를 base로 잡고 쌓아 올린다 풀이 자체는 어렵지 않았던거 같은데 처음에 탑-다운 방식으로 소스를 구성하니 처음엔 메모리초과, 그다음엔 시간초과가 발생했다 결국 다운-탑 방식으로 구성했다 소스 1234567891011121314151617181920212223#include #include #include #include using namespace std; int dp[100001]; int main(void){ int N; scanf("%d",&N); for(int i=1;i
PS/백준 2021. 3. 29. 08:58
[백준/C++] 11052번 - 카드 구매하기

오늘의 문제! https://www.acmicpc.net/problem/11052 입력 첫째 줄에 N이 주어짐 둘째 줄에 N개의 Pi가 주어짐 풀이 기존에 풀었던 dp문제 중 가장 기본적인 틀 형식으로 풀었다 카드가 최종 장수가 되면 리턴, 전체 카드팩의 종류를 다 확인하면 -1을 리턴 처음 result는 현재 카드팩을 구매하지 않고 다음 카드팩을 확인 두번째 result는 현재 카드팩을 구매하고 다시 확인 소스 123456789101112131415161718192021222324252627282930313233343536373839 #include #include #include using namespace std; int N;int P[1001];int dp[1001][1001]; int func(..
PS/백준 2021. 3. 29. 08:49
[백준/C++] 2339번 - 석판자르기

오늘의 문제! https://www.acmicpc.net/problem/2339 입력 첫째 줄에 N이 주어짐 둘째 줄부터 N개의 줄에 석판의 상태가 주어짐 풀이 전체 map에서 불순물을 찾고 불순물을 기준 가로, 세로로 자는 경우를 찾는다 불순물을 찾은경우 석판을 잘라야 하는데 자를 수 없는 경우를 먼저 판단한다 1번 - 불순물과 보석이 1개씩인 경우 2번 - 불순물만 있거나 불순물과 보석이 둘다 없는 경우 3번 - 불순물이 없고 보석이 2개 이상인 경우 4번 - 불순물을 자르고자 하는 방향에 보석이 있는 경우 5번 - 가로로 자르려고 하는데 불순물이 가장 위 또는 가장 아래에 있는 경우 6번 - 세로로 자르려고 하는데 불순물이 가장 왼쪽 또는 가장 오른쪽에 있는 경우 총 6가지의 경우는 석판을 자를 수..
PS/백준 2021. 3. 25. 00:11
[백준/C++] 1992번 - 쿼드트리

오늘의 문제! https://www.acmicpc.net/problem/1992 입력 첫째 줄에 N이 주어짐 둘째 줄부터 N개의 줄 동안 길이 N인 문자열이 들어옴 풀이 1번 (x0,y0)~(xi,yi) 까지 0 또는 1중 하나의 값으로 이루어 있는지 확인, 둘중 하나의 값으로 되어 있으면 해당 값 출력 2번 0과1로 섞여있을 경우는 좌상,우상,좌하,우하로 나누어 다시 1번 판별 이때 좌상 들어가기전 " ( " 출력 / 우하 끝나고 " ) " 출력 소스 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748 #include #include using namespace std; char map[65][65..
PS/백준 2021. 3. 23. 20:48
[백준/C++] 1725번 - 히스토그램

오늘의 문제! https://www.acmicpc.net/problem/1725 입력 첫째 줄에 N이 주어짐 둘째 줄부터 N개 동안 히스토그램의 높이가 주어진다 풀이 라이님의 분할정복에서 분할정복의 이해를 위해 예제로 설명해주신 문제였다 기본적인 풀이법은 여기에서 설명한 것과 비슷하다 1번 mid를 기준으로 왼쪽 중 최대 넓이가 나오는 경우 2번 mid를 기준으로 오른쪽 중 최대 넓이가 나오는 경우 3번 mid를 기준으로 왼쪽과 오른쪽이 겹쳐서 최대 넓이가 나오는 경우 소스 123456789101112131415161718192021222324252627282930313233343536373839404142 #include #include using namespace std; int H[100000]; ..
PS/백준 2021. 3. 20. 19:13
[백준/C++] 2104번 - 부분배열 고르기

오늘의 문제! https://www.acmicpc.net/problem/2104 입력 첫째 줄에 N이 주어짐 둘째 줄에 N개의 정수들이 주어짐 풀이 해당 문제는 분할정복으로 해결했고 3가지 경우로 나뉘어진다. 1번 mid를 기준으로 왼쪽의 배열에서 최대값이 나오는 경우 2번 mid를 기준으로 오른쪽 배열에서 최대값이 나오는 경우 3번 mid를 기준으로 왼쪽과 오른쪽이 겹쳐서 최대값이 나오는 경우 따라서 우선은 1번 2번은 mid기준으로 나누고 최대값을 구하면되니 먼저 구해준다 그다음 3번을 구하는데 mid를 기준으로 왼쪽과 오른쪽중 큰값을 우선적으로 선택해서 결과값을 구해보고 최대값이면 갱신을 해준다. 물론 이때 값이 최소 원소값보다 작으면 해당 값을 갱신해주고 해당 확인은 현재의 배열 전체를 확인식으로..
PS/백준 2021. 3. 19. 13:48
[백준/C++] 1629번 - 곱셈

오늘의 문제! https://www.acmicpc.net/problem/1629 입력 첫째 줄에 A B C가 주어짐 풀이 (A x B) % C 는 ((A%C) * (B%C)) % C 와 같다 그리고 B가 짝수이면 A의 B제곱은 A의 B/2제곱의 2제곱으로 나타낼 수 있다. B가 홀수 이면 A의 B/2제곱의 2제곱에 A를 곱한게 A의 B제곱이 된다. 이때 주의 점은 A B C가 최대 2,147,483,647 이므로 자료형 선택에 있어 조심해야한다. A가 20억 B가 2일때 C가 21억이면 결과를 구하는 과정에서 A * A가 400억이 되어 int 를 사용하면 중간과정에서 오버플로우가 발생한다. 소스 123456789101112131415161718192021222324252627 #include #incl..
PS/백준 2021. 3. 18. 19:47
[백준/C++] 1493번 - 박스 채우기

오늘의 문제! https://www.acmicpc.net/problem/1493 입력 첫째 줄에 length width height 주어짐 둘째 줄에 N이 주어짐 셋째 줄부터 N개의 줄에 Ai와 Bi가 주어짐 풀이 박스에 들어가는 가장 큰 경우의 큐브부터 해결을 하여 최종적으로 1x1x1의 큐브로 줄여가면서 해결한다. 최초의 박스를 L x W x H 로 한다면 이때 들어갈 수 있는 큐브의 수는 각 L W H 를 큐브의 길이로 나눈 수로 구할 수 있다. 예를 들어 4 4 8 박스에 4 4 4 큐브를 넣는 수는 4/4 * 4/4 * 8/4 로 2개이다. 그리고 4 4 8 박스에 2 2 2 큐브를 넣는 수는 4/2 * 4/2 * 8/2 로 16개 이다. 이때 4 4 4 큐브를 최대로 넣고 2 2 2 큐브로 넣..
PS/백준 2021. 3. 17. 22:22
1 2
공지사항
최근에 올라온 글
최근에 달린 댓글
Total
Today
Yesterday
링크
TAG more
«   2025/02   »
일 월 화 수 목 금 토
1
2 3 4 5 6 7 8
9 10 11 12 13 14 15
16 17 18 19 20 21 22
23 24 25 26 27 28
글 보관함