KoreanFoodie's Study
SW 역량테스트 - [모의 SW 역량테스트] 벌꿀채취 문제 풀이/해답/코드 (C++ / JAVA) 본문
Data Structures, Algorithm/SW 역량테스트
SW 역량테스트 - [모의 SW 역량테스트] 벌꿀채취 문제 풀이/해답/코드 (C++ / JAVA)
GoldGiver 2020. 9. 29. 11:21
SW 역량 테스트 준비를 위한 핵심 문제들을 다룹니다!
해답을 보기 전에 문제를 풀어보시거나, 설계를 하고 오시는 것을 추천드립니다.
코드에 대한 설명은 주석을 참고해 주세요 :)
문제 링크 : swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5V4A46AdIDFAWu
해답 코드 :
// c++
#include <stdio.h>
#include <memory.h>
int input[10][10];
int n, m, c, res;
int max(int a, int b) {
return (a > b) ? a : b;
}
// (x,y) 좌표부터 m개의 꿀통을 선택해서 얻을 수 있는 최대 가격을 구하는 재귀 함수
void getMaxPrice(int x, int y, int cnt, int sum, int price) {
if (sum > c) return;
res = max(res, price);
if (cnt == m) return;
getMaxPrice(x, y + 1, cnt + 1, sum + input[x][y], price + input[x][y] * input[x][y]);
getMaxPrice(x, y + 1, cnt + 1, sum, price);
}
int solve(int x, int y) {
res = 0;
getMaxPrice(x, y, 0, 0, 0);
int priceA = res;
// 두번째 사람이 고른 벌통 M개의 비용구하기
int priceB = 0;
int j = y + m;
for (int i = x; i < n; i++, j = 0) {
for (; j < n - m + 1; j++) {
res = 0;
getMaxPrice(i, j, 0, 0, 0);
priceB = max(priceB, res);
}
}
return priceA + priceB;
}
int main() {
int t;
scanf("%d", &t);
for (int tc = 1; tc <= t; tc++) {
scanf("%d %d %d", &n, &m, &c);
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
scanf("%d", &input[i][j]);
}
}
int maxPrice = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n - m + 1; j++) {
maxPrice = max(maxPrice, solve(i, j));
}
}
printf("#%d %d\n", tc, maxPrice);
}
}
// java
import jdk.nashorn.internal.ir.Block;
import java.util.Scanner;
import java.io.FileInputStream;
/*
사용하는 클래스명이 Solution 이어야 하므로, 가급적 Solution.java 를 사용할 것을 권장합니다.
이러한 상황에서도 동일하게 java Solution 명령으로 프로그램을 수행해볼 수 있습니다.
*/
class sumBlock {
public int sum;
public int x;
public int y;
sumBlock(int total, int b, int c) {
sum = total;
x = b;
y = c;
}
int get_x() {
return x;
}
int get_y() {
return y;
}
}
class Solution
{
static int[][] honey = new int[10][10];
static boolean overlap() {
return true;
}
static int getMax(int[] test, int start, int end) {
int max = test[start];
for (int i = start; start <= end; i++) {
max = Math.max(test[i], max);
}
return max;
}
static int getSum(int[] test, int start, int end, int c) {
if (start == end) {
if (test[start] <= c) return test[start] * test[start];
else return 0;
}
if (test[start] <= c) {
return Math.max(test[start]*test[start] + getSum(test, start+1, end, c-test[start]) , getSum(test, start+1, end, c));
} else {
return getSum(test, start+1, end, c);
}
}
public static void main(String args[]) throws Exception
{
/*
아래의 메소드 호출은 앞으로 표준 입력(키보드) 대신 input.txt 파일로부터 읽어오겠다는 의미의 코드입니다.
여러분이 작성한 코드를 테스트 할 때, 편의를 위해서 input.txt에 입력을 저장한 후,
이 코드를 프로그램의 처음 부분에 추가하면 이후 입력을 수행할 때 표준 입력 대신 파일로부터 입력을 받아올 수 있습니다.
따라서 테스트를 수행할 때에는 아래 주석을 지우고 이 메소드를 사용하셔도 좋습니다.
단, 채점을 위해 코드를 제출하실 때에는 반드시 이 메소드를 지우거나 주석 처리 하셔야 합니다.
*/
//System.setIn(new FileInputStream("res/input.txt"));
/*
표준입력 System.in 으로부터 스캐너를 만들어 데이터를 읽어옵니다.
*/
Scanner sc = new Scanner(System.in);
int T;
T=sc.nextInt();
/*
여러 개의 테스트 케이스가 주어지므로, 각각을 처리합니다.
*/
for(int test_case = 1; test_case <= T; test_case++)
{
int max_result = -9999;
int N, M, C;
N = sc.nextInt();
M = sc.nextInt();
C = sc.nextInt();
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
honey[i][j] = sc.nextInt();
}
}
int[][] BlockSum = new int[N][N-M+1];
// calculate the Sum of each block
for (int i = 0; i < N; i++) {
for (int j = 0; j < N-M+1; j++) {
BlockSum[i][j] = getSum(honey[i], j, j+M-1, C);
}
}
// without overlapping, get the maximum combination
for (int i = 0; i < N; i++) {
for (int j = 0; j < N-M+1; j++) {
for (int k = i; k < N; k++) {
for (int l = 0; l < N-M+1; l++) {
if (i == k && j + M >= l) continue;
else max_result = Math.max(max_result, BlockSum[i][j] + BlockSum[k][l]);
}
}
}
}
System.out.println("#" + test_case + " " + max_result);
}
}
}
SW 역량테스트 준비 - [모의 SW 역량테스트] 풀이 / 코드 / 답안 (C++ / JAVA)
SW 역량테스트 준비 - C++ 코드, Java 코드
SW 역량테스트 준비 - 백준 알고리즘 문제
'Data Structures, Algorithm > SW 역량테스트' 카테고리의 다른 글
SW 역량테스트 - [백준] 연구소 문제 풀이/해답/코드 (C++ / JAVA) (0) | 2020.09.29 |
---|---|
SW 역량테스트 - [모의 SW 역량테스트] 등산로 조성 문제 풀이/해답/코드 (C++ / JAVA) (0) | 2020.09.29 |
SW 역량테스트 - [백준] 치킨 배달 문제 풀이/해답/코드 (C++ / JAVA) (0) | 2020.09.29 |
SW 역량테스트 - [모의 SW 역량테스트] 보호 필름 문제 풀이/해답/코드 (C++ / JAVA) (0) | 2020.09.29 |
SW 역량테스트 - [모의 SW 역량테스트] 디저트 카페 문제 풀이/해답/코드 (C++ / JAVA) (0) | 2020.09.29 |
Comments