์๊ทผ์ด๋ ์์ฆ ์คํ๊ณต์ฅ์์ ์คํ์ ๋ฐฐ๋ฌํ๊ณ ์๋ค. ์๊ทผ์ด๋ ์ง๊ธ ์ฌํ๊ฐ๊ฒ์ ์คํ์ ์ ํํ๊ฒ Nํฌ๋ก๊ทธ๋จ์ ๋ฐฐ๋ฌํด์ผ ํ๋ค. ์คํ๊ณต์ฅ์์ ๋ง๋๋ ์คํ์ ๋ด์ง์ ๋ด๊ฒจ์ ธ ์๋ค. ๋ด์ง๋ 3ํฌ๋ก๊ทธ๋จ ๋ด์ง์ 5ํฌ๋ก๊ทธ๋จ ๋ด์ง๊ฐ ์๋ค.
์๊ทผ์ด๋ ๊ท์ฐฎ๊ธฐ ๋๋ฌธ์, ์ต๋ํ ์ ์ ๋ด์ง๋ฅผ ๋ค๊ณ ๊ฐ๋ ค๊ณ ํ๋ค. ์๋ฅผ ๋ค์ด, 18ํฌ๋ก๊ทธ๋จ ์คํ์ ๋ฐฐ๋ฌํด์ผ ํ ๋, 3ํฌ๋ก๊ทธ๋จ ๋ด์ง 6๊ฐ๋ฅผ ๊ฐ์ ธ๊ฐ๋ ๋์ง๋ง, 5ํฌ๋ก๊ทธ๋จ 3๊ฐ์ 3ํฌ๋ก๊ทธ๋จ 1๊ฐ๋ฅผ ๋ฐฐ๋ฌํ๋ฉด, ๋ ์ ์ ๊ฐ์์ ๋ด์ง๋ฅผ ๋ฐฐ๋ฌํ ์ ์๋ค.
์๊ทผ์ด๊ฐ ์คํ์ ์ ํํ๊ฒ Nํฌ๋ก๊ทธ๋จ ๋ฐฐ๋ฌํด์ผ ํ ๋, ๋ด์ง ๋ช ๊ฐ๋ฅผ ๊ฐ์ ธ๊ฐ๋ฉด ๋๋์ง ๊ทธ ์๋ฅผ ๊ตฌํ๋ ํ๋ก๊ทธ๋จ์ ์์ฑํ์์ค.
์ ๋ ฅ
์ฒซ์งธ ์ค์ N์ด ์ฃผ์ด์ง๋ค. (3 โค N โค 5000)
์ถ๋ ฅ
์๊ทผ์ด๊ฐ ๋ฐฐ๋ฌํ๋ ๋ด์ง์ ์ต์ ๊ฐ์๋ฅผ ์ถ๋ ฅํ๋ค. ๋ง์ฝ, ์ ํํ๊ฒ Nํฌ๋ก๊ทธ๋จ์ ๋ง๋ค ์ ์๋ค๋ฉด -1์ ์ถ๋ ฅํ๋ค.
1) ๊ฐ์ฅ ์์ ๊ฐ์๋ฅผ ๊ตฌํ ์ํด์๋ 5๋ฅผ ์ต๋ํ ์ด ํ, 3์ ์ฌ์ฉํด์ผ ํจ
2) n์ 5๋ก ๋๋ ๋ชซ์ ๊ตฌํ ํ, ๋ชซ์ ํ๋์ฉ ์ค์ฌ๊ฐ๋ฉฐ ๋๋จธ์ง๊ฐ 3์ผ๋ก ๋๋์ด ๋จ์ด์ง๋ ์ง ํ์ธ
3) 3,5์ ์กฐํฉ์ผ๋ก ๋๋์ด ๋จ์ด์ง๋ ์์๋ flag = 1์ ํด์ค
1) n์ 5๋ก ๋๋ ๋ชซ์ ๊ตฌํ ํ, ๋ชซ์ ํ๋์ฉ ์ค์ฌ๊ฐ๋ฉฐ ๋๋จธ์ง๊ฐ 3์ผ๋ก ๋๋์ด ๋จ์ด์ง๋ ์ง ํ์ธ
for(int i=share; i>=0; i--) {
int rest = n - (5*i);
if(rest%3 == 0) {
flag = 1;
share = i;
break;
}
}
2) 3,5์ ์กฐํฉ์ผ๋ก ๋๋์ด ๋จ์ด์ง๋ ์์๋ flag = 1์ ํด์ค
if(rest%3 == 0) {
flag = 1;
share = i;
break;
}
import java.io.*;
public class Greedy_9 {
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());
int flag = 0;
int share = n/5;
for(int i=share; i>=0; i--) {
int rest = n - (5*i);
if(rest%3 == 0) {
flag = 1;
share = i;
break;
}
}
share+=(n-share*5)/3;
if(flag == 1)
System.out.println(share);
else
System.out.println(-1);
}
์ฑ๊ณต~