🔗 문제 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] = ..

🔗 문제 SW Expert Academy SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 🖍 풀이 DFS는 시간초과고 BFS이라고 생각해서 풀면 오답이다. (경험담) 왜냐하면 생각해보면 map의 좌표 (x, y)까지 오는 경로는 다양하다. 가는 길이 0, 1로만 이루어진 것이 아니기 때문에 첫 방문이 최소 경로라고 단정지을 수 없다. 그래서 상하좌우로 이동하면서 (x, y)까지 걸린 시간을 계속해서 갱신해주어야 한다. visited[x][y]로 재방문를 판단하기는 하지만 그냥 갱신인지 신규인지만 판단하는 용도로 사용해줬다. 다익스트라의 개념을 알고 있으면 내 풀이를 이해하는데 도움됨 💾 소스 #include #..

🔗 문제 https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV18KWf6ItECFAZN SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 🖍 풀이 set 라이브러리의 특성을 이용하면 쉽게 풀 수 있다. set은 중복을 제외하고, 오름차순으로 자동 정렬해주는 특성이 있다. 먼저 문자열을 다 쪼개어서 저장해준다. substr(i, j) i 위치에서부터 j개를 자르는 substr 함수 for(int i=0; i T; for(int tc=1; tc> N >> str; std::set set; for(int i=0; i

🔗 문제 SW Expert Academy SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 🖍 풀이 완전 탐색으로 돌려줬다. 완전 탐색 문제를 풀 때는 조건문으로 필요없는 반복을 줄이는 것이 중요하다. for문으로 교환해줄 때 i, j의 조건을 보자. j는 i보다 더 큰 수로만 증가하여 중복되는 교환횟수를 줄였다. visited[ 교환 후 숫자 ] [교환횟수] 로 중복 교환 횟수를 줄여주었다. 💾 소스 #include #include #include // memset #include // swap #define MAX 1000000 std::string answer; bool visited[MAX][11]; //..