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 역량테스트 준비 - 백준 알고리즘 문제

 
Comments