developer-ellen
인간 디버거의 로그 찍기
developer-ellen
전체 방문자
오늘
어제
  • 분류 전체보기 (217)
    • 회고록 (0)
    • 취뽀 및 커리어 여정의 Stack (2)
      • SSAFY 7기 (2)
    • 프로그래밍공부 (24)
      • c++ (0)
      • JAVA (3)
      • Spring (5)
      • design pattern (3)
      • BackDB (1)
      • Servlet&JSP (3)
      • Vue (4)
      • JPA (4)
      • Infra (1)
      • Linux (0)
    • AI (3)
      • papers (3)
      • trend (0)
    • 프로젝트진행 (0)
      • 데이터베이스 (0)
      • 서버개발 (0)
      • 인공지능 (0)
      • 하루정리 (0)
    • 포트폴리오 (0)
    • 알고리즘 (158)
      • 알고리즘문풀 (155)
      • 알고리즘공부 (3)
    • 통계공부 (15)
      • 시계열분석 (15)
      • 회귀분석 (0)
    • CS (14)
      • 컴퓨터네트워크 (4)
      • 운영체제 (8)
      • 데이터베이스 (2)
    • 주저리주저리 (0)
      • 필사 (0)
    • 취업관련정보 (0)

블로그 메뉴

  • 홈
  • 태그
  • 방명록

공지사항

인기 글

태그

  • 삼성코테기출
  • 삼성코테기출자바풀이
  • 시계열분석
  • 데이터분석
  • 삼성코테구현문제추천
  • 시계열
  • 삼성코테자바꿀팁
  • 삼성코테자바풀이
  • 코테파이썬
  • SW역량테스트파이썬
  • ARIMA모형
  • 통계학
  • 운영체제인터럽트
  • BOJ파이썬풀이
  • MA모형
  • c++디자인패턴
  • 삼성코테준비
  • 백준파이썬풀이
  • 삼성코테자바준비
  • SW역량테스트파이썬풀이
  • 카카오코테
  • 삼성코테파이썬준비
  • AR모형
  • 삼성코테파이썬
  • 삼성코테파이썬풀이
  • Arima
  • 카카오코테java풀이
  • 삼성코테구현풀이
  • c++ 빌더 패턴
  • 통계분석

최근 댓글

최근 글

티스토리

hELLO · Designed By 정상우.
developer-ellen

인간 디버거의 로그 찍기

알고리즘/알고리즘문풀

BOJ - 기타줄 1049번 (JAVA)

2022. 1. 28. 22:25

❓ 문제 - 백준 기타줄 1049번 - JAVA 풀이법

 

출처 

(https://www.acmicpc.net/problem/1049)

 

1049번: 기타줄

첫째 줄에 N과 M이 주어진다. N은 100보다 작거나 같은 자연수이고, M은 50보다 작거나 같은 자연수이다. 둘째 줄부터 M개의 줄에는 각 브랜드의 패키지 가격과 낱개의 가격이 공백으로 구분하여 주

www.acmicpc.net

 

 

 

 

📝 문제해결법

1. 이 문제는 Greedy(탐욕법)으로 알고리즘을 풀었다.

  • 기타줄 N개를 사기 위해 최소값을 구할 때 고려해야 할 경우는 다음이다.
  • 1> 팩(6개 묶음)에서 최소가격일 때 기타줄에 사야하는 갯수만큼 팩을 구매할 때
  • 2> 1개씩 파는 기타줄에서 최소 가격일 때 사야하는 기타줄의 갯수만큼 구매할 때
  • 3> 팩(6개 묶음)에서 최소가격으로 기타줄에 사야하는 갯수만큼 팩을 구매하고 남은 갯수들은 1개씩 파는 기타줄의 최소가격으로 구매할 때
  • 3번의 경우 팩으로 사는 갯수를 줄이고 1개씩 파는 기타줄을 더 사서 n만큼 사는 경우도 고려할 수 있지 않다 -> 그럼 최소가격이 고려되지 않는 것이다.  

 

2. 문제를 풀면서 느낀점

  • 그리디는 최솟값, 최대값을 구한 후 그것을 이용해서 답을 구하는 문제가 많은 것 같다. 

 

💻 소스코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Arrays;

public class Main {

	public static void main(String[] args) throws IOException{
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		
		
		
		String[] s1 = br.readLine().split(" ");
		int n = Integer.parseInt(s1[0]);
		int m = Integer.parseInt(s1[1]);
		
		int ans = Integer.MAX_VALUE;
		int min_pack = Integer.MAX_VALUE;
		int min_one = Integer.MAX_VALUE;
		
		for(int i=0;i<m;i++) {
			String[] s = br.readLine().split(" ");
			int a = Integer.parseInt(s[0]);
			int b = Integer.parseInt(s[1]);
			min_pack = Math.min(min_pack, a);
			min_one = Math.min(min_one, b);
			
		}
		
		ans = Math.min(ans, (n/6+1)*min_pack);
		ans = Math.min(ans, min_one*n);
		
		ans = Math.min(ans, (n/6)*min_pack + (n%6)*min_one);
		
		
		bw.write(String.valueOf(ans));
		bw.flush();
		bw.close();

		
	}

}

'알고리즘 > 알고리즘문풀' 카테고리의 다른 글

BOJ - 벽 부수고 이동하기 2206번 (JAVA)  (0) 2022.02.07
BOJ - 팰린드롬 만들기 1213번 (JAVA)  (0) 2022.02.02
BOJ - A->B 16953번 (JAVA)  (0) 2022.01.25
BOJ - 시간 관리 1263번 (JAVA)  (0) 2022.01.24
SW Expert Academy - 등산로 조정 (python)  (0) 2021.10.23
    '알고리즘/알고리즘문풀' 카테고리의 다른 글
    • BOJ - 벽 부수고 이동하기 2206번 (JAVA)
    • BOJ - 팰린드롬 만들기 1213번 (JAVA)
    • BOJ - A->B 16953번 (JAVA)
    • BOJ - 시간 관리 1263번 (JAVA)
    developer-ellen
    developer-ellen

    티스토리툴바