소프티어

Tc5만 틀리는데 이유가 뭘까요... 도저히 모르겠네요 ( Java )

public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = new StringTokenizer(br.readLine()); int w = Integer.parseInt(st.nextToken()); int b = Integer.parseInt(st.nextToken()); int[][] arr = new int[b][2]; for(int i=0;i<b;i++){ st = new StringTokenizer(br.readLine()); int gw = Integer.parseInt(st.nextToken()); int worth = Integer.parseI...

Java 풀이 시, 2번 4번 테케 시간 초과하는 경우

정렬 방법을 바꿔 볼 필요가 있씁니다. 저는 `Arrays.sort(arr, Comparator.comparingInt((int[] a) -> a[1]).reversed())` 로 정렬했을 때는 2번 시간초과 였고, (long형으로 바꾸면 4번도 초과) `Arrays.sort(arr, (a, b) -> Integer.compare(b[1], a[1]))` 로 바꾸니 통과됐습니다.

c++로 풀었습니다.

#include<iostream> #include<vector> #include <algorithm> using namespace std; bool CompareBySecond(const std::pair<int, int> &a, const std::pair<int, int> &b) { return a.second > b.second; } int main(int argc, char** argv) { std::vector<std::pair<int,int>> goldVec; int result = 0; int bag = 0; int totalN = 0; cin >> bag >> totalN; for(int i = 0; i < totalN; ++i) { int a,b; cin >> a >>b; std::pair<int,int> goldPa...

시간초과가 발생합니다.

import sys howmany=list(map(int,input().split(" "))) totalweight=howmany[0] nomjewel=howmany[1] money=0 weightlist=[] pricejewel=[] for i in range(nomjewel): tellprice=list(map(int,input().split(" "))) weightlist.append(tellprice[0]) pricejewel.append(tellprice[1]) while totalweight>0: a=max(pricejewel) b=pricejewel.index(max(pricejewel)) c=weightlist[b] if totalweight>c: totalweight=totalweight-c money=money+(a*c) pr...

TC 2, 5번 안되는 이유 알려주세요ㅠ

import java.io.*; import java.util.*; public class Main { private static List<Map.Entry<Integer, Integer>> sortPriceAndWeight(Map<Integer, Integer> metalMap) { List<Map.Entry<Integer, Integer>> entryList = new LinkedList<>(metalMap.entrySet()); entryList.sort(new Comparator<Map.Entry<Integer, Integer>>() { @Override public int compare(Map.Entry<Integer, Integer> o1, Map.Entry<Integer, Integer> o2) { return o2.getValue() - o...

단순 수학문제네요

학부 때 배운 배낭문제 생각했는데, 그냥 수학 문제네요. 가치가 큰 것부터 더하다가 무게만큼 더할 수 없을 때는 그 차이만큼 더해주면 되는 거였습니다.

동적 계획법 (dp)로 푸는 방법 없을까요?

일반적인 배낭 문제처럼 풀고 싶은데 잘 안되네요ㅜㅜ 같이 고민해주시면 감사하겠습니다ㅜㅜ #include <stdio.h> int max(int a, int b) { return (a > b) ? a : b; } int main(void) { int W, N; scanf("%d %d", &W, &N); int M[N], P[N]; for (int i = 0; i < N; i++) { scanf("%d %d", &M[i], &P[i]); } int dp[N + 1][W + 1]; int decide=0; for (int i = 0; i <= N; i++) { for (int j = 0; j <= W; j++) { if (i == 0 || j == 0) { dp[i][j] = 0; } else if (M[i - 1] <= j) { dp[i][j] = max(M[i-1]*P[i - 1] + dp[i - 1][j - M[i - 1]], dp[i - 1][j]); if(decide!=M[...

코드 공유 드립니다. 더 이쁘게 만들 수 있는 방법 공유 주시면 감사히 참고하겠습니다.

#include<iostream> #include<vector> #include<algorithm> using namespace std; typedef struct{ int W; int M; } st_stone; class stones{ public: stones() {} void insert(int W, int M){ st_stone temp_stone = {.W = W, .M = M}; items.push_back(temp_stone); } void Sort(){ sort(items.begin(), items.end(), [](const st_stone &a, const st_stone &b){ return a.M < b.M; }); } int Max_Money(int weight){ int money = 0; this->Sort(); while (weight != 0){ st_stone stone = items.back(); if (stone.W >= weight){ mo...

파이썬 오류 코드 조언 요청드립니다 ㅜㅜ

import sys # 배냥의 무게, 귀금속의 종류 W, N = list(map(int, input().split())) weight_list = [] price_list = [] for i in range(N): M, P = list(map(int, input().split())) # 금속의 무게, 무게당 가격 weight_list.append(M) # 무게 리스트 price_list.append(P) # 가격 리스트 sorted_weight = sorted(weight_list) # 무게별 정렬 리스트 final_price = 0 # 최종 가격 compare_weight = W # 잔여 무게 for min_weight in sorted_weight: # 작은 무게부터 하나씩 가져온다. min_price = price_list[weight_list.index(min_weight)] # 해당 무게에 대한 가격 찾기 if compare_weight >= min_weight: # ...

테스트 케이스 2번 5번 질문드립니다.

import sys total, n = map(int, sys.stdin.readline().split()) bag=[] for _ in range(n): m, p = map(int, sys.stdin.readline().split()) bag.append([p,m]) result = 0 bag.sort(reverse = True) idx = 0 while total>0 and idx < n: if total - bag[idx][1] >=0: total -= bag[idx][1] result += bag[idx][0] * bag[0][1] else: result += total * bag[idx][0] total = 0 idx += 1 print(result) 테케 2번 5번에서 오답이라 뜨고, 시간도 3초가 넘어가는데 시간 관련된 문제는 금속의 무게와 무게당 가격 리스트를 받아오는 곳에서 리스트 컴프리헨션을 사용하지 않고 리스트에 추가한 후 정렬을 해서 그런 건가요?? 시간초...