www.acmicpc.net/problem/16637

 

16637번: 괄호 추가하기

첫째 줄에 수식의 길이 N(1 ≤ N ≤ 19)가 주어진다. 둘째 줄에는 수식이 주어진다. 수식에 포함된 정수는 모두 0보다 크거나 같고, 9보다 작거나 같다. 문자열은 정수로 시작하고, 연산자와 정수가

www.acmicpc.net

1.풀이방법

 

- 수식과 정수를 나누는 작업을 따로 하지는 않았고 모두 index를 통해서 접근하였습니다.

 

- 모든 경우의 수를 재귀를 통해서 구현한 후 연산하시면 됩니다.

 

- 처음에 문제조건을 파악하고 무조건 dp라고 생각하고 반복문을 이용해서 바텀업 방식으로 구현을 했는데

 

- 계속 틀렸다고 나와서 방식을 약간 바꿨는데......하 아직도 첫 소스에서는 어떤 사항을 잡지 못하는지

 

- 모르겠네요...... 역시 테스트케이스는 되는데 제출하면 틀릴 때는 참 예외사항 발견하기가 어렵네요

 

- 두번째로 틀린 소스도 올릴테니 지적과 조언좀 부탁드려요...(뭐가 잘못 되었을 까요......ㅠ)

 

 

 

 

 

2. 주의사항

 

- 어이가 없지만.......1일 경우 if문을 걸어 그냥 바로 출력하게끔 했는데,,,,, return 0;을 안줘서

 

- 계쏙 88퍼 쯤에서 틀렸습니다....ㅎ...한참 고민했는데 어이가 없었네요.....기본적인 실수를 줄이도록...해야겠습니다...

 

 

 

 

 

3. 나의 코드

 

<정답 코드>

#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
using namespace std;


int N;
string inputs;
vector<long long> maxresult;
long long tmpnum;

long long cal(long long num1, long long num2, char c) {
	if (c == '+') { return num1 + num2; }
	else if (c == '-') { return num1 - num2; }
	else {
		return num1 * num2;
	}
}
void dfs(int index, long long nowvalue) {
	if (index >= N - 1) {
		maxresult.push_back(nowvalue);
		return;
	}
	tmpnum = cal(nowvalue, inputs[index + 2] - '0', inputs[index + 1]);
	dfs(index + 2, tmpnum);
	if (index + 4 <= N - 1) {
		long long first = cal(inputs[index + 2] - '0', inputs[index + 4] - '0', inputs[index + 3]);
		tmpnum = cal(nowvalue, first, inputs[index + 1]);
		dfs(index + 4, tmpnum);
	}
}
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	cin >> N;
	cin >> inputs;
	if (N == 1) { cout << inputs[0] - '0' << "\n"; return 0; }
	dfs(0, inputs[0] - '0');
	sort(maxresult.begin(), maxresult.end());
	cout << maxresult[maxresult.size() - 1] << "\n";
	return 0;
}

 

 

<오답 코드>  ---- 지적해주세요 !ㅠㅠ

#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
using namespace std;

long long dp[20]; // 결과를 저장할 테이블
int N;
string inputs;

long long cal(long long num1, long long num2, char c) {
	if (c == '+') { return num1 + num2; }
	else if (c == '-') { return num1 - num2; }
	else {
		return num1 * num2;
	}
}
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	cin >> N;
	cin >> inputs;
	dp[0] = inputs[0] - 48;
	dp[2] = cal(inputs[0] - 48, inputs[2] - 48, inputs[1]);
	if (N == 1) { cout << dp[0] << "\n"; return 0; }
	if (N == 3) {cout << dp[3] << "\n"; return 0;}
	for (int i = 4; i < N; i += 2) {
		long long first = cal(inputs[i - 2] - 48, inputs[i] - 48, inputs[i - 1]);
		first = cal(dp[i - 4], first, inputs[i - 3]);
		long long second = cal(dp[i - 2], inputs[i] - 48, inputs[i - 1]);
		dp[i] = max(first, second);
	}
	cout << dp[N - 1] << "\n";
	return 0;
}

'알고리즘 문제풀이 > 완탐' 카테고리의 다른 글

백준 17135 [C++]  (0) 2020.10.21
백준 17136 [C++]  (0) 2020.10.20
백준 17070 [C++]  (0) 2020.10.14
백준 17281 : 야구 [C++]  (0) 2020.10.13
백준 1748 : 수 이어 쓰기 1  (0) 2020.03.24

www.acmicpc.net/problem/17406

 

17406번: 배열 돌리기 4

크기가 N×M 크기인 배열 A가 있을때, 배열 A의 값은 각 행에 있는 모든 수의 합 중 최솟값을 의미한다. 배열 A가 아래와 같은 경우 1행의 합은 6, 2행의 합은 4, 3행의 합은 15이다. 따라서, 배열 A의

www.acmicpc.net

 

 

1. 풀이 방법

 

- 경우의 수는 명령의 순서에 따라 결과가 달라지므로 순열로 구했습니다.

 

 

- 회전을 구현해야 하는데, 바깥쪽 부터 한 겹씩 회전을 시키는 순으로 했고

=

  맨 안쪽에 남은 하나는 오른쪽으로 가려고 하는데 이미 방문한 곳이면 break 하게끔 하였습니다.

 

 

-코드가 많이 길어졌네요...ㅠ

 

 

 

 

2.주의할 점.

 

- 코드가 길어지다보니 처음 짠 부분에서 이곳 저곳에서 문제가 발생...

   디버깅을 한참했습니다...

 

 

-디버깅을 아예 안하기는 쉽지 않겠지만 처음 짤 때 그래도 좀 세심하게 해야겠네요...

 

 

-그리고 (r-s,r+s) 입력이 이런식 이기때문에 행과 열의 수는 모두 홀수 입니다.

(처음에 짝수 개도 되는 경우의 수도 생각하고 짰었는데...풀다보니 발견...)

 

 

- 조건에 따른 문제를 정확하게 파악해야겠습니다...

 

 

 

 

3. 나의코드

 

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

int N, M;
int K,r,s;
int doublearr[51][51]; //본 2차원 배멸 (변화 x)
int caculdoublearr[51][51]; //case별 결과값을 뽑아내기 위한 배열
int copydoublearr[51][51]; //이동을 위해 값을 복사해놓을 임시배열
bool check[51][51];
bool selected[7];
vector<int> resultmin;

struct rcs {
	int r,c,s;
};
vector<rcs> command; //입력받은명령
vector<rcs> casecommand; // 각 경우의수 (시뮬레이션 돌릴)

void input() { // 입력받는 함수		
	cin >> N >> M >> K;
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= M; j++) {
			cin >> doublearr[i][j];
		}
	}
	rcs tmp;
	for (int i = 0; i < K; i++) {
		cin >> tmp.r >> tmp.c >> tmp.s;
		command.push_back(tmp);
	}
}
void copyarr() { // 원본배열은 그대로 두고 복사해서 사용 (각 테스트케이스마다 써야하므로)
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= M; j++) {
			copydoublearr[i][j] = doublearr[i][j];
			caculdoublearr[i][j] = doublearr[i][j];
		}
	}
}
void initcheck() { // 방문배열 초기화
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= M; j++) {
			check[i][j] = false;
		}
	}
}
void copycal() { //한번회전한 배열을 계산을 위한 배열에 복사
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= M; j++) {
			copydoublearr[i][j] = caculdoublearr[i][j];
		}
	}
}
void turnarr(int r, int c, int s) { //회전을 구현
	int x = r - s;
	int y = c - s;
	int tmpcount = 0;
	int totalcount = 8 * s; //연산해야하는 횟수 한 바퀴에
	char dir = 'R';
	initcheck();
	while (1) {
		if (totalcount == tmpcount) { //바깥한바퀴 -> 안쪽 바퀴로 들어감
			x += 1; y += 1; s -= 1; totalcount = 8 * s;
			tmpcount = 0;
		}
		if (dir == 'R') {
			if (check[x][y+1] == true) { copycal(); break;
			}
			caculdoublearr[x][y + 1] = copydoublearr[x][y];
			tmpcount++;
			check[x][y] = true;
			y += 1;
			if (y == c + s) { dir = 'D'; }
		}
		else if (dir == 'D') {
			caculdoublearr[x + 1][y] = copydoublearr[x][y];
			tmpcount++;
			check[x][y] = true;
			x += 1;
			if (x == r + s) { dir = 'L'; }
		}
		else if (dir == 'L') {
			caculdoublearr[x][y - 1] = copydoublearr[x][y];
			tmpcount++;
			check[x][y] = true;
			y -= 1;
			if (y == c - s) { dir = 'U'; }
		}
		else {
			caculdoublearr[x - 1][y] = copydoublearr[x][y];
			tmpcount++;
			check[x][y] = true;
			x -= 1;
			if (x == r - s) { dir = 'R'; }
		}
	}
}
int getmin() { //배열의 최소값을 뽑아내는 함수
	int mini = 5001;
	for (int i = 1; i <= N; i++) {
		int tmpsum = 0;
		for (int j = 1; j <= M; j++) {
			tmpsum += caculdoublearr[i][j];
		}
		if (tmpsum < mini) { mini = tmpsum; }
	}
	return mini;
}
void relocating() { //명령을 수행 (회전명령)
	copyarr();
	for (int i = 0; i < K; i++) {
		turnarr(casecommand[i].r, casecommand[i].c, casecommand[i].s);
	}
	resultmin.push_back(getmin());
}
void simulation(int n) { //순열 경우의 수 생성
	if (n == K) {
		relocating(); 
		return;
	}
	for (int i = 0; i < command.size(); i++) {
		if (selected[i] == true) continue;
		selected[i] = true;
		casecommand.push_back(command[i]);
		simulation(n+1);
		casecommand.pop_back();
		selected[i] = false;
	}
}



int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	input();
	simulation(0);
	sort(resultmin.begin(), resultmin.end());
	cout << resultmin[0];
	return 0;
}

'알고리즘 문제풀이 > 구현' 카테고리의 다른 글

백준 2033 C++  (0) 2020.11.25
백준 14890 [C++]  (0) 2020.10.21
백준 15686 [C++]  (0) 2020.10.17
백준 3190 [C++]  (0) 2020.10.17
백준 18406 [C++]  (0) 2020.10.16

www.acmicpc.net/problem/15686

 

15686번: 치킨 배달

크기가 N×N인 도시가 있다. 도시는 1×1크기의 칸으로 나누어져 있다. 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다. 도시의 칸은 (r, c)와 같은 형태로 나타내고, r행 c열 또는 위에서부터 r번째 칸

www.acmicpc.net

 

1. 풀이방법

 

- 문제를 꼼꼼히 읽고, 전체 치킨 집 중에서 M개를 선택하는 경우의 수 (조합)

 

- 을 구해서 그 CASE마다 도시의 치킨거리를 구해보면 되는 문제.

 

 

 

2. 주의할점

 

- 딱히없음.

 

 

 

3.나의 코드

 

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

int N, M;
int map[51][51];
vector<pair<int, int>> chikenstore; //전체 치킨집을 저장할 좌표 집합
vector<pair<int, int>> chosenstore; //선택된 치킨집을 저장할 좌표 집합(M개)
vector<pair<int, int>> home; //집의 위치를 저장할 좌표 집합 (x,y) 
vector<int> result; //결과

void InputMap() { //입력받는 함수
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) {
			cin >> map[i][j];
			if (map[i][j] == 2) {
				pair<int, int> tmp;
				tmp.first = i; tmp.second = j;
				chikenstore.push_back(tmp);
			}
			else if (map[i][j] == 1) {
				pair<int, int> tmp;
				tmp.first = i; tmp.second = j;
				home.push_back(tmp);
			}
		}
	}
}

int abs(int num1, int num2) { //절대값 반환
	if (num1 - num2 > 0) { return num1 - num2; }
	else { return num2 - num1; }
}

int loadsum(int x1, int y1, int x2, int y2) { //거리 계산
	return abs(x1, x2) + abs(y1, y2);
}

void caculatechickenload() { //도시의 치킨거리를 계산
	int sum = 0;
	for (int i = 0; i < home.size(); i++) { //집마다
		int min = 3000;
		for (int j = 0; j < chosenstore.size(); j++) { //치킨집에 대하여 거리계산(가장 가까운 치킨집=치킨거리)
			if (min > loadsum(home[i].first, home[i].second, chosenstore[j].first, chosenstore[j].second)) {
				min = loadsum(home[i].first, home[i].second, chosenstore[j].first, chosenstore[j].second);
			}
		}
		sum += min;
	}
	result.push_back(sum);
}

void Mchickenstore(int index) {
	if (chosenstore.size() == M) { // M개를 골랐다면 치킨거리계산 시작
		caculatechickenload();
		return;
	}
	for (int i = index; i < chikenstore.size(); i++) { //조합 경우의 수
		chosenstore.push_back(chikenstore[i]);
		Mchickenstore(i + 1);
		chosenstore.pop_back();
	}
}
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	cin >> N >> M;
	InputMap();
	Mchickenstore(0);
	sort(result.begin(), result.end()); //가장 최소 도시치킨거리 출력
	cout << result[0] << "\n";
	
	return 0;
}

 

 

'알고리즘 문제풀이 > 구현' 카테고리의 다른 글

백준 2033 C++  (0) 2020.11.25
백준 14890 [C++]  (0) 2020.10.21
백준 17406 [C++]  (0) 2020.10.18
백준 3190 [C++]  (0) 2020.10.17
백준 18406 [C++]  (0) 2020.10.16

www.acmicpc.net/problem/3190

 

3190번: 뱀

 'Dummy' 라는 도스게임이 있다. 이 게임에는 뱀이 나와서 기어다니는데, 사과를 먹으면 뱀 길이가 늘어난다. 뱀이 이리저리 기어다니다가 벽 또는 자기자신의 몸과 부딪히면 게임이 끝난다. 게임

www.acmicpc.net

1. 풀이방법

 

- 문제의 그대로를 구현하면 되는 문제인데.. 아마 20대 중후반 분들은 한번쯤은 해보시지 않았을까....

 

- 저의 방법은 머리와 꼬리의 현재좌표를 계속 갱신하는 것인데...

 

- 핵심은 머리가 지나가면서 자신이 어디로 지나갔었는지를 지도에 기록을 해놓아야 하는 것.

 

- 사과가 없어서 꼬리가 짧아 져야 할 경우 지도에 기록해둔 머리가 갔던 방향(꼬리 좌표에서)을 확인하고 그 방향으로       이동합니다.. (directionjirung[][])

 

- 방향전환 명령어는 큐를 이용해서 pair의 first(시간) 이 게임시간과 일치할 때 pop을 하여 썼습니다.

 

 

 

2. 주의할 점

 

- 하.....전 꽤 오래 걸렸는데....아이디어를 생각하고 구현한게 어려운게 아니라...

 

- 변수를 수정할때 조심해야할 것...

tailx+=directionjirung[tailx][taily]; //이 따구로 하면 변경된 tailx가

taily+=directionjirung[tailx][taily]; //여기에 반영되기 때문에 매우 엉망인 값이 나옵니다..

 

- <변경된 코드는 이렇습니다>

int tmpx=tailx;

int tmpy=taily;

tailx+=directionjirung[tmpx][tmpy];

taily+=directionjirung[tmpx][tmpy];

 

기본적인 실수를 하고도 못찾아서 한참을 찾았네요.....지도도 출력하고...;;

 

이제부터 더 주의해서 세심하게 코드를 짜야겠습니다

 

감을 다시 잡아야겠네요....

 

 

3. 나의코드

 

#include<iostream>
#include<vector>
#include<queue>
using namespace std;

int map[101][101]; //사과가 있는지 여부를 알기 위해
int jirung[101][101];//지렁이의 현재위치
int directionjirung[101][101]; //꼬리를 위한 지렁이가 그 좌표에서 보고있던 방향을 기록
int N;
int K;
int dx[4] = {0,1,0,-1}; //동남서북
int dy[4] = {1,0,-1,0};
int direction=0; //지렁이가 보고있는 방향(처음엔 동쪽 보고있다.)
int gamesecond;
int L;
int headx, heady,tailx,taily;
queue<pair<int, char>> dq;

void setapple() {
	int x, y;
	for (int i = 0; i < K; i++) {
		cin >> x >> y;
		map[x][y] = 1; //사과가 존재하는 위치
	}
}
void setqueue() {
	pair<int, char> tmppair;
	for (int i = 0; i < L; i++) {
		cin >> tmppair.first >> tmppair.second;
		dq.push(tmppair);
	}
}

int main() {
	cin >> N >> K;
	setapple();
	cin >> L;
	setqueue();
	headx = 1; heady = 1; tailx = 1; taily = 1;
	jirung[1][1] = 1;
	while (1) {
		while (1) {
			if (dq.empty() == false && gamesecond == dq.front().first) {
				if (dq.front().second == 'L') { //왼쪽 회전
					direction = (direction + 3) % 4;
				}
				else {//오른쪽 회전
					direction = (direction + 1) % 4;
				}
				dq.pop();
			}
			else break;
		}
		gamesecond++;

		directionjirung[headx][heady] = direction; //꼬리를위해 방향을 기록먼저 !
		headx += dx[direction]; heady += dy[direction];
		if (headx <= 0 || heady <= 0 || headx > N || heady > N || jirung[headx][heady] == 1) {  break; } //종료조건 (map의 범위 1~N)

		jirung[headx][heady] = 1; //머리가 도착한 곳 표시
		if (map[headx][heady] == 1) { //사과가 있다면
			map[headx][heady] = 0; 
		}
		else {
			jirung[tailx][taily] = 0; //사과가 없다면 꼬리좌표 지워짐
			int tmptailx = tailx;
			int tmptaily = taily;
			tailx = tailx + dx[directionjirung[tmptailx][tmptaily]]; //꼬리의 위치 업데이트 (머리가 지나갈때 간 방향으로 업데이트)
			taily = taily + dy[directionjirung[tmptailx][tmptaily]];
		}
	}
	cout << gamesecond << "\n";
			return 0;
}

'알고리즘 문제풀이 > 구현' 카테고리의 다른 글

백준 2033 C++  (0) 2020.11.25
백준 14890 [C++]  (0) 2020.10.21
백준 17406 [C++]  (0) 2020.10.18
백준 15686 [C++]  (0) 2020.10.17
백준 18406 [C++]  (0) 2020.10.16

+ Recent posts