[풀이]백준 (16917, 16918,16922)
문제풀이
양념 반 후라이드 반(16917, 브루트포스)
현진 치킨에서 판매하는 치킨은 양념 치킨, 후라이드 치킨, 반반 치킨으로 총 세 종류이다. 반반 치킨은 절반은 양념 치킨, 절반은 후라이드 치킨으로 이루어져있다.
- 양념 치킨 한 마리의 가격은 A원
- 후라이드 치킨 한 마리의 가격은 B원
- 반반 치킨 한 마리의 가격은 C원이다.
상도는 오늘 파티를 위해 양념 치킨 최소 X마리, 후라이드 치킨 최소 Y마리를 구매하려고 한다. 반반 치킨을 두 마리 구입해 양념 치킨 하나와 후라이드 치킨 하나를 만드는 방법도 가능하다. 상도가 치킨을 구매하는 금액의 최솟값을 구해보자.
회고
어쩐지 설명을 들을 때 보다 조건이 까다롭더라니 양념치킨최소 X마리 후라이드치킨 최소 Y마리였다…
내가 생각한 조건은
- 마리수는 항상 X+Y여야한다. (이게문제였어)
- 반반치킨은 2마리 단위로 구매한다.
- 아래와 같은 조건이 들어갔다.
for(z=0; z<=x+y; z++){
if(z%2==0 && x-z/2>=0 && y-z/2>=0 )
근데 가만보니 반반치킨이 말도안되게 싸면 그냥 다 반반치킨으로 사서 최소마리수만 충족시키면 되는 것이었던 것이었음…
정답코드
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
int a, b, c, x, y, z, value=987654321;
cin >> a >> b >> c >> x >> y;
int xTemp = x;
int yTemp = y;
for(z=0; z<=max(x,y)*2; z++){
if(z%2==0)
{
x = max(0,x-z/2);
y = max(0,y-z/2);
int temp = a*x + b*y + c*z;
value = min(value, temp);
x= xTemp;
y= yTemp;
}
}
cout << value;
}
봄버맨(16918)
시뮬레이션문제 (문제에 써 있는 것을 그대로 구현하면 끝남)
- 크기가 R*C인 직사각형 격자판
- 폭탄은 3초뒤에 폭발하고 인접한 네칸과 함께 빈 칸이 됨
- 인접칸에 폭탄이 있는 경우 연쇄반응 없이 빈 칸이 된다.
- 1초 : 봄버맨은 아무것도 하지않는다.
- 2초 : 폭탄이 설치되어 있지 않은 모든 칸에 폭탄을 설치한다.
- 3초 : 처음에 있던 폭탄이 모두 폭발한다.
- 2초와 3초에 있던 일을 반복한다.
빈칸은 . 폭탄은 0으로 주어지며 R개의 줄에 N초가 지난 후의 격자판 상태를 출력한다.
회고
시간별로 나눈 다음 공통으로 수행해야 하는 작업(시간–)부분에서 실수가 있었다. 노가다성이 짙은 문제라 귀찮은 것은 복붙했는데… 나중에 어떤 문제를 풀어야하는지 알려주시면 다시 시도해봐도 좋을 것 같다.
#include <iostream>
#include <vector>
#include <algorithm>
#include <string.h>
using namespace std;
int main() {
int dx[] = {0,0,1,-1};
int dy[] = {1,-1,0,0};
int r, c, n;
cin >> r >> c >> n;
int timeTable[r][c]; // 빈 칸: 0, 폭탄: 터지기까지 남은 시간
for (int i=0; i<r; i++) {
string s;
cin >> s;
for (int j=0; j<c; j++) {
if (s[j] == '.') {
timeTable[i][j] = 0;
} else {
timeTable[i][j] = 2;
}
}
}
for(int t=2; t<=n; t++){
// //CASE1: 1초 단위(아무것도 안함)
// if(t%3==1)
// {
// for(int i=0; i<r; i++){
// for(int j=0; j<c; j++){
// if(timeTable[i][j]>0) timeTable[i][j]--;
// }
// }
// }
//CASE3: 3초 단위(처음 3초는 폭발하고 그 뒤는 아무런 일도 없다.)
// else{
// for(int i=0; i<r; i++){
// for(int j=0; j<c; j++){
// if(timeTable[i][j]>0) timeTable[i][j]--;
// }
// }
// }
// //CASE2: 2초 단위(빈 칸을 폭탄으로 채우고 폭탄인 곳은 시간이 흐른다)
//-----위는 중복코드-------
// else
if(t%2==0)
{
for (int i=0; i<r; i++) {
for (int j=0; j<c; j++) {
if (timeTable[i][j] == 0)
{
timeTable[i][j] = 3; // 폭탄이 아닌 곳에 폭탄 설치
}
else if (timeTable[i][j] > 0)
{
timeTable[i][j]--; // 폭탄인 곳은 시간이 흐름
}
}
}
}
else
{
//폭발
for(int i=0; i<r; i++){
for(int j=0; j<c; j++){
if(timeTable[i][j]==1){
for(int k=0; k<4; k++){
int x= i+dx[k];
int y= j+dy[k];
if (0 <= x && x < r && 0 <= y && y < c) {
if (timeTable[x][y] != 1) { // 인접한 칸이 1초 남은 폭탄이 아니면, 이번에 터지는 폭탄이 아님 또는 빈 칸
timeTable[x][y] = 0;
}
}
}
}
}
}
//시간 감소 (t%2 인 경우에는 이미 시간감소를 했다!.. 여기서 틀렸네)
for (int i=0; i<r; i++) {
for (int j=0; j<c; j++) {
if (timeTable[i][j] > 0) {
timeTable[i][j] -= 1;
}
}
}
}
}
//출력
for (int i=0; i<r; i++) {
for (int j=0; j<c; j++) {
if (timeTable[i][j] == 0) {
cout << '.';
} else {
cout << 'O';
}
}
cout << '\n';
}
}
[중요]로마 숫자 만들기(16922, 브루트포스)
- 로마 숫자는 I, V, X, L을 사용한다. (각 1, 5, 10 ,50)
- 로마숫자 N개를 사용해서 만들 수 있는 서로다른 수의 개수를 구하는 문제(N<=20)
- 정말 최애에에에에대의 경우 4^20까지 나온다. (1억 훌쩍 넘음) 즉, 방법이 잘못되었다 혹은 방법의 수를 줄인다.
순서만 다른 것은 의미가 없다! 따라서 경우의 수는 N^4이다.(XXL = XLX = LXX) 즉, 순서보다 선택이 중요하다. I= A개, V= B개, X= C개, L= D개 선택하자.
- 가능한 방법의 수를 더 줄일 수 있다.
- A + B + C + D = N;
- A + 5B + 10C + 50D;
- D = A, B, C를 구하면 고정되는 값이므로 삼중포문 O(N^3)까지 줄일 수 있다.
회고
포문 만드는게 생각보다 어렵다… 다시 풀어볼 것…하
#include <iostream>
#include <vector>
#include <algorithm>
#include <string.h>
using namespace std;
bool check[1001];
int main() {
int n, Answer=0;
cin >> n;
for (int i=0; i<=n; i++) {
for (int j=0; j<=n-i; j++) {
for (int k=0; k<=n-i-j; k++) {
int l = n-i-j-k;
int sum = i+(5*j)+(10*k)+(50*l);
check[sum]=true;
}
}
}
for(int i=1; i<=1000; i++){
if(check[i]) Answer++;
}
cout << Answer;
}
댓글남기기