풀이 보관함

🔗 문제 16987번: 계란으로 계란치기 16987번: 계란으로 계란치기 원래 프로그래머의 기본 소양은 팔굽혀펴기를 단 한 개도 할 수 없는 것이라고 하지만 인범이는 3대 500을 넘기는 몇 안되는 프로그래머 중 한 명이다. 인범이는 BOJ에서 틀린 제출을 할 때마다 턱 www.acmicpc.net 🖍 풀이 문제 정리 내구도와 무게를 가진 계란 N개가 있다. 왼쪽부터 깨지지 않은 계란을 집어들고 다른 안 깨진 계란을 깰 시도를 한다. 이 때! 내가 깨질 수도 있고 다른 계란이 깨질 수도 있다. 두 계란의 내구도는 상대 계란의 무게만큼 감소한다. 내구도가 음수가 되면 그 계란이 깨진다. 이걸 깰 계란이 없을 때까지 반복한다. 깰 수 있는 계란이 여러 개 있을 때 탐욕 기법을 이용해서 풀어야 하나 고민을 했..

🔗 문제 https://softeer.ai/practice/info.do?idx=1&eid=540&sw_prbl_sbms_sn=158428 Softeer 연습문제를 담을 Set을 선택해주세요. 취소 확인 softeer.ai 백준 뿌요뿌요같은 문제인데 아직 시간초과를 해결하지 못 했다. 알고리즘 단톡방에 올렸는데 아무도 대답해주지 않았고 (…) 나처럼 풀었는데 성공한 사람은 꼭 알려주면 좋겠다. 꼭! 🖍 풀이 N*N 구역에서 같은 색깔의 위치로 면적과 몇 대가 있는지 구해야 한다. N*N 구역에서 사라질 수 있는 차량 종류는 여러 가지이므로 DFS를 사용한다. 같은 색깔이 주변에 있는지 탐색하는 것은 BFS를 사용한다. 같은 종류의 차량이 있는 면적을 구해야 하기 때문에 최대 및 최소 좌표와 같은 차량의 ..

🔗 문제 1103번: 게임 1103번: 게임 줄에 보드의 세로 크기 N과 가로 크기 M이 주어진다. 이 값은 모두 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에 보드의 상태가 주어진다. 쓰여 있는 숫자는 1부터 9까지의 자연수 또는 www.acmicpc.net 🖍 풀이 안 올리려다가 나같은 실수한 사람이 있을까봐 풀이를 올려봅니다.. 근데 나밖에 없을 듯 ㅎ DFS에서 DP를 통한 가지치기가 필요한 문제였다. 처음에는 BFS로 풀다가 방향 경로마다 visited를 생성할 수 없다는 걸 깨닫고 DFS로 전환했다. 문제에서 동전이 이동한 후 적혀있는 X만큼 이동하라는 조건이 있다. 근데 나는 dir 방향 한.칸.씩. 이동해서 틀렸다 .. 암만 생각해봐도 왜 틀린지 모르겠어서 질문 올리기 직전에 ..

🔗 문제 16235번: 나무 재테크 16235번: 나무 재테크 부동산 투자로 억대의 돈을 번 상도는 최근 N×N 크기의 땅을 구매했다. 상도는 손쉬운 땅 관리를 위해 땅을 1×1 크기의 칸으로 나누어 놓았다. 각각의 칸은 (r, c)로 나타내며, r은 가장 위에서부터 www.acmicpc.net 제한 1 ≤ N ≤ 10 1 ≤ M ≤ N^2 1 ≤ K ≤ 1,000 1 ≤ A[r][c] ≤ 100 1 ≤ 입력으로 주어지는 나무의 나이 ≤ 10 입력으로 주어지는 나무의 위치는 모두 서로 다름 🖍 풀이 처음에는 나무를 list에 저장하고 폐사할 경우 -1로 표기하고 해마다 정렬했는데 시간초과였다. 나이 오름차순으로 양분을 먹이려고 정렬을 이용했고, 새로 생기는 나무를 push_front()로 넣어도 시간초과..

문제 https://www.acmicpc.net/problem/1699 1699번: 제곱수의 합 어떤 자연수 N은 그보다 작거나 같은 제곱수들의 합으로 나타낼 수 있다. 예를 들어 11=32+12+12(3개 항)이다. 이런 표현방법은 여러 가지가 될 수 있는데, 11의 경우 11=22+22+12+12+12(5개 항)도 가능하다 www.acmicpc.net 풀이 dp[i]: N을 제곱수로 나눴을 때 가장 작은 제곱 항수를 저장하는 변수 - dp[i]은 초기값으로 N을 가진다. (1 제곱 * N항 ) 그리고 나서 재귀관계식을 찾아주었다. 나는 N이 13일 때까지 쭉 나열하며 재귀관계식을 찾을 수 있었다. - N에서 나눠떨어지는 숫자가 있으면 나눠떨어지는 숫자는 무조건 1이다. (4, 8, 16, 25..) ..

🔗 문제 Softeer Softeer 연습문제를 담을 Set을 선택해주세요. 취소 확인 softeer.ai 🖍 풀이 1000ms 안에 풀어야 하는데 시간 초과 때문에 못 풀었다. 나는 최대 1082ms로 시간 초과다. 진짜 진짜 조금만 더 줄이면 되는데 아쉬워서 일단 포스팅한다.......ㅠ 특정 점수를 초과하는 개수로 등수 표현 for(int i=0; i

🔗 문제 2156번: 포도주 시식 2156번: 포도주 시식 효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 같은 두 가지 규 www.acmicpc.net 🖍 풀이 완전 탐색으로 풀면 시간 초과가 나와서 동적 계획법으로 풀어야 하는 문제였다. (경험담) i번째 잔에는 선택권이 2개가 있다. 마시거나 마시지 않거나 통합 DP[i] = std::max( std::max(DP[i-2], DP[i-3] + W[i-1]) + W[i], // i번째 마신 경우 DP[i-1] // i번째 안 마신 경우 ); 💾 소스 #include #include const int MAX = 10010; int..

🖍 문제 9465번: 스티커 9465번: 스티커 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 n (1 ≤ n ≤ 100,000)이 주어진다. 다음 두 줄에는 n개의 정수가 주어지며, 각 정수는 그 위치에 해당하는 스티커의 www.acmicpc.net 📄 풀이 이 문제를 바로 풀 수 있는 사람이 있을까? 풀 때마다 암기력으로 극복하는 중인데 이게 맞나 싶다. 💾 소스 #include #include int main() { int T; std::cin >> T; int sticker[2][100001]; int dp[2][100001]; dp[0][0] = 0; dp[1][0] = 0; while (T--) { int n; std::cin >> n; for (int i =..

🔗 문제 SW Expert Academy SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 1258. [S/W 문제해결 응용] 7일차 - 행렬찾기 🖍 풀이 전체 행렬 크기(N)는 최대 100 고맙게도 최소 행렬 개수 문제도 아니며 서브 행렬들은 붙어있지도 않다. 사각형으로 존재한다. → 물질이 들어있는 위치를 찾으면 어떤 사각형으로 잘라야 최소 용기 개수인지 고민할 필요 없다. → 그 위치에서 서브 행렬 크기만 찾아내면 됨 이중포문으로 0이 아닌 위치를 찾는다. 그 위치에서 최대 사각형 크기를 구한다. R x C 와 크기를 저장한다. 찾은 사각형을 0으로 변경한다. 출력의 조건을 맞추기 위해 연산자 오버라이딩을 ..

🔗 문제 SW Expert Academy SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com [S/W 문제해결 응용] 5일차 - 단순도금비용 🖍 풀이 🚩 주의: 단순도금비용은 Pass지만, 도금 비용은 Fail이에요. 문제를 보면 가장 큰 필름부터 붙이는 것이 좋겠다는 생각이 든다. 1) 먼저 손상 개수별로 최소 비용으로 수리할 수 있는 필름 크기를 알아보자. 9~5개는 사이즈가 3인 필름을 붙이는 것이 최소 비용 4~2개는 사이즈가 2인 필름을 붙이는 것이 최소 비용 1개는 사이즈가가 1인 필름을 붙이는 것이 최소 비용 이를 토대로 손상 개수 범위를 지정했다. const int size_range[3][2] = ..