그리디

https://www.acmicpc.net/problem/11399

11399번: ATM

static void Main(string[] args)
        {
            int peopleNum = int.Parse(Console.ReadLine());
            int[] times = Array.ConvertAll(ReadLine().Split(), int.Parse);
            int result = 0;
            Array.Sort(times);
            for(int i =1; i<= times.Length; i++)
            {
                for(int j = 0; j< i; j++)
                {
                    result += times[j];    
                }
            }
            WriteLine(result);
        }

 

https://www.acmicpc.net/problem/11047

11047번: 동전 0

오랜만이라 겁먹었는데 이 문제는 한번에 잘 풀려서 다행이었다

1. 내가 푼 코드

 static void Main(string[] args)
        {
//(입력)
            string[] input = ReadLine().Split();
            int kindNum = int.Parse(input[0]);
            int target = int.Parse(input[1]);
            int result = 0;
            int[] kindOfCoins = new int[kindNum];

            for(int i =0; i < kindNum; i++)
            {
                kindOfCoins[i] = int.Parse(ReadLine());
            }         

//(입력)
            for(int i = kindOfCoins.Length-1; i>= 0; i--)
            {
                if(target <= 0)
                {
                    break; //target이 0이하 되면 반복탈출
                }
                if(kindOfCoins[i] > target)
                {
                    continue; //ex) target = 4200원, kindOfCoins = 5000원이면 스킵
                }
                int repeatCnt = target / kindOfCoins[i]; //ex) target 4200원, kinofCoins[i] = 1000일 때 몫4 이므로 아래 연산 4번 반복
                for (int j =0; j< repeatCnt; j++)
                {
                    target -= kindOfCoins[i];
                    result++;
                }
            }
            Console.WriteLine(result);

2.  다른 분 코드

 

target 이 0이 아닐 때 반복하는 while문에 모든 동전 종류를 순회하는 for문이 들어가있는데, 

while의 반복조건이 충족되면  for문이 배열크기만큼 매 반복마다 돌아가기 때문에 복잡도는 직접 푼 코드가 나을 것 같긴 하다.  

using System;

namespace c_bjcoding
{
    class MainClass
    {
        public static void Main(string[] args){
            int count = 0;
            string[] input = Console.ReadLine().Split(' ');

            int num =int.Parse(input[0]);
            int target_value = int.Parse(input[1]);

            int[] values = new int[num];

            for (int i = 0; i < num; i++){
                values[i] = int.Parse(Console.ReadLine());
            }
            while(target_value != 0){
                for (int j = num-1; j >= 0 ;j--){
                    if(target_value - values[j] >= 0){
                        target_value -= values[j];
                        count++;
                        break;
                    }
                }   
            }
            Console.WriteLine(count);
        }
    }