코딩무식자 전공생

문제 출처: https://www.acmicpc.net/problem/2206

풀이

공주님을 구해라! https://www.acmicpc.net/problem/17836 와 비슷한 문제로, 3차원배열을 이용하여 풀었습니다.

문제가 똑같아보여서 출력하는것만 수정하고(시작점과 도착점도 시간포함) 제출했는데 틀렸습니다. 

공주님 문제는 검을 얻으면 도착할 때 까지 벽(1)을 빈칸(0)으로 간주할 수 있지만, 이 문제는 벽을 안부시거나 딱 한번만 부시기 때문에 

벽을부순 이후와 검을 먹은 이후의 시뮬레이션의 차이가 있으므로 어느정도 수정해야했습니다.

3차원 배열은 벽을 부시지않았을때(0), 벽을 부셨을 때(1)를 표현하기위해 선언하였고 4가지 경우에대해서만 구현하면됩니다.

실제로는 2가지만 구현하면됩니다.

1. 벽을 만났는데 벽을 부순적이없다.

->벽을 뚫었는지를 나타내는 get변수(0:뚫지않았음 1:뚫었음)를 1로 바꿔서 벽을 뚫었다고 표현해주고, 벽을 부순자리의 visited값을 벽 부수기 직전자리의 visited값+1으로 수정시킵니다. 이 때 visited[ny][nx][get]=visited[y][x][get]+1으로 선언하면  현재 벽을 부수지않고 도착한 좌표를 직전자릿값+1으로 바꾼다고도 볼수 있으므로, 

벽을 부수고 도착한 좌표임을 나타내기위해 visited[ny][nx][get+1]=visited[y][x][get]+1로 선언합니다.

2. 빈 칸을 만났는데 방문하지않은곳이다.

직전 좌표값 +1 처리해줍니다. visited[ny][nx][get]=visited[y][x][get]+1 해줍니다. 

1번 처리로 인해 벽을 부순좌표에서 넘어온것과 벽을 부수지않은 좌표에서 넘어온것이 구분됩니다.

3. 벽을 만났는데 벽을 부순적이있다.

-> 어떠한 연산도 하지않고 넘어갑니다. (continue or 분기)

4. 빈 칸을 만났는데 방문한적이 있는곳이다.

-> 어떠한 연산도 하지않고 넘어갑니다. (continue or 분기)

마지막으로 모든 연산 후 큐가 비었음에도 도착좌표에 도착하지않았다면 도착이 불가능함을 의미하므로 -1을 출력합니다.

코드

문제 출처: https://www.acmicpc.net/problem/17836

풀이

여러가지 bfs문제를 풀면서 특정 조건이 있을 때 3차원배열을 이용할 수 있음을 배웠습니다.

예를들어 

1. 길을 탐색할 때 벽을 뚫고가거나 벽을 뚫지않고 갈때 도착점에 도달시 최단거리

2. 검을 먹고 도착하거나 검을 먹지않고 도착할 때 최단거리

같은 경우, 기존의 2차원visited배열을 3차원으로 visited[크기][크기][2]로 선언해서 인덱스가 0이고 값이0일 때 벽을 뚫지않고/검을 먹지않고 그 좌표에 도착하지않았음을 의미하고 인덱스가 1이고 값이 1일때 벽을 뚫고/검을 먹고 도착하였다로 해석 할 수 있습니다. 되게 유용한 것 같습니다.

문제에대해 풀이순서대로 작성해보았습니다.

1. visited배열 선언시 3차원으로 선언하여 검을먹고/먹지않고를 표현할 수 있게한다. 

2. y좌표,x좌표, 걸린시간, 검을획득했는지여부를 구조체로 저장하여 큐에담아서 bfs를 돌린다.

3. 검을 만나면 get을 1로 바꿔주고, 도착점에 도착하면 탈출하여 값 출력하기

일반적인 bfs는 다돌려놓고 도착점의 좌표의 visited배열값을 출력하지만 이 문제는 검을 먹고도착/먹지않고 도착 2가지경우가 있으므로 도착했을 때, 큐에 아직 길을 가고있는 좌표들이있던말던 상관없이 도착하기만 하면 그게 곧 최단거리이므로 탈출하여 값 출력한다. 

그렇기 때문에 문제예제처럼 16s가 걸리던 10s가 걸리던 더 짧은 시간을 비교할필요가없음

4. visited배열에 진행시간을 수정해나갈 때 주의하기

일반적인 bfs는 visted[ny][nx]=visited[y][x]+1하여 최단거리를 찾지만, 이 문제는 검을먹고/먹지않고 가는 좌표가 검획득여부에따라 다름

무슨말이냐면, 같은좌표를 가도, 3차원배열이기 때문에 먹지않고 도착하는좌표와 먹고 도착하는좌표의 값은 서로 다름 

따라서 문제예제를보면, 위처럼 코드작성 시 검을 먹은위치는 6이아닌 0이된다. 

검 먹을 때 get이 1이되므로 검을 먹은좌표가 "검을먹은상태에서 검을먹기직전까지온 시간+1로 해석된다.

검의 좌표는 검을 먹지않은 상태에서 검을 먹기직전까지 온 시간 +1이 되어야한다.

따라서 visited[ny][nx][get]=cnt+1로 작성해야한다.

5. 벽 뚫고 가는것 표현하기

굳이 벽을뚫고가는 모션을 표현할 필요없고, 검을 먹은 뒤부터는 모든 좌표를 갈 수 있으므로 다음좌표를 방문했는지만 확인하면된다.

6. 정답 출력시 ans범위 조심하기

ans<=t인지만 확인하면 ans=0일 때 Fail 대신 0이 출력될수 있으므로 , ans>0 or ans>=1의 조건을 붙여준다.

코드

문제 출처: https://www.acmicpc.net/problem/11051

풀이

nCr == n-1Cr + n-1Cr-1로 표현할 수 있고 아래 내용들만 알고있으면 쉽게 dp 2차원배열로 풀수 있습니다.

1. r이 1이면 n에 상관없이 무조건 n 

2. n==r이면 무조건 1

3. r이 0이면 무조건 1

2중for문에서 i가 3, j=2부터 시작되는 이유는

i가 3보다 작을 때는 위의 3가지 조건들을 미리 계산해놓으면 아래 식 까지 계산되어서 굳이 또 계산할 필요가 없기 때문입니다.

1 1

2 1

2 2

3 1

코드

문제 출처: https://www.acmicpc.net/problem/1339

풀이

백트래킹으로 분류된 문제지만 이렇게풀어도될 것 같은데? 해보니 풀린 문제입니다. 

문자열 S를 앞에서부터 10의 제곱꼴로 저장해놓고 9,8,7,6...순으로 곱하면서 최댓값을 구할 수 있습니다. 아래에 문제 풀이 순서대로 적어보았습니다.

1. int형 알파벳 배열 선언하기

알파벳 갯수를체크하기위함이 아닌 입력받은S의 첫번째 알파벳부터 10의 제곱꼴로 하여 저장하기위해 선언. n번 만큼 반복해서 값을 누적시킵니다.

2. 최댓값을 구하기위해 알파벳 배열에 담긴 값들을 큰값부터 정렬시키기

3. 정렬시킨 알파벳배열의 값들이 최댓값 순으로 정렬되어있으므로 각 값들을 9,8,7,6...순으로 곱해나가기. 결국 최종sum이 최댓값이 되어있음

코드

문제 출처: https://www.acmicpc.net/problem/1182

풀이

s를 위한 부분수열(부분집합)을 만들 때, 해당 인덱스값을 더하거나, 더하지않는 경우가 있습니다.

즉 저 두 경우에대해서 s를 만들 수 있는 모든 후보군들이 구해집니다.

주의할 것은 공집합(0)처리입니다. 

s가 0일때, 아래코드를 돌리면 정답+1갯수가 출력되는데, 시작하는 sum이 0부터 시작되므로, 최초의 연산 시, 부분수열을 구하지않았음에도 

재귀함수를 통해(더하지 않았을 때의 함수)언젠가는 최초의 sum=0인값이 s와 동일하다고 인식되어 경우의 수가 하나 추가됩니다. 

그러므로, s=0일 때는 모든 경우를 구하고 한가지경우를 빼준 경우가 답이됩니다.

코드

문제 출처: https://www.acmicpc.net/problem/1018

풀이

규칙을 찾아서 풀어도되지만 8*8 체스판을 검정색,흰색이 각각 먼저 나오는 두 가지 버전으로 그려놓고 하나씩 비교하며 풀었습니다.

주의할점 :

1. 최소값이 매번 갱신되어야하므로 min_val 변수선언하여 비교 

2. black_change,white_change도 매번 갱신되므로 전역변수가 아닌 지역변수로 선언

3. string이 아닌 c언어로 풀 때 인덱스 조심(50 X  51부터)

4. 체스판을 검색하는 함수(black,white)에서 인덱스 [i-y][j-x]가 탐색을 시작한 좌표와 그려놓은 체스판의 첫번째 요소부터 같이 움직이는것을 알기

코드

문제 출처: https://www.acmicpc.net/problem/1759

두 가지 방법으로 풀어보았습니다. 

첫번 째 풀이는 배열에 담은 요소가 L개가 됐을 때 배열에서 자음과 모음을 매번 확인하는데, 입력범위가 커질 때 비효율적일 것같습니다.

두 번째 풀이는 string을 이용해서 풀었습니다.

풀이1

문제 출처: https://www.acmicpc.net/problem/16637

풀이

1. 연산자갯수와 숫자의 갯수를 각각의 배열에 담는다.

길이가 최대 19이므로 연산자9개, 피연산자 10개까지 나올 수 있다. 피연산자의 개수는 index1, 연산자의 갯수는 index2가 된다. 

내 풀이는 연산자기준으로, 연산자를 모두쓰게되면 계산 종료후 최댓값을 갱신한다.

2. 괄호쳐서 계산하는 것 잘 이해하기(괄호 치는 것만으로

대충 괄호를 쳐서 계산하는것과 괄호를 치지않고 쭉 계산해나가는 식을 작성해야함은 알 수 있다.  

괄호를 안치고 계산하는 연산은 아래 코드처럼, 연산후, dfs를 계속 돌리면된다. 

//앞에서부터 계산하기
	int res = func(sum, num[cnt + 1],op[cnt]);
	//dfs돌려서 확인하기(더 계산할 수 있는지)
	dfs(res, cnt + 1);

괄호를 쳐서 계산하는연산을 보자. 

1+2*3 일 때 괄호를 치려면, 일단 연산자가 최소 2개는 있어야한다.( 1+2 꼴일때는 괄호치는것과 안치는것 결과값같음)

따라서 1+(2*3)꼴이 되게하려면 현재 사용되고있는 연산자+1 인덱스의 연산자가 존재할 때 계산해야한다.

즉, 현재 cnt=0이라 op[cnt]=='+'인데, 1+(2*3)처럼 괄호를 치려면, cnt+1(op[cnt+1]=='*')가 아직 사용되지않았을 때다.

그리고나서 2*3을 구한뒤(a), 1과 a를 더해주면 1+(2*3)을 계산하게된다. 괄호안치는 연산 1+2*3은 이미 위의 코드로 잘 계산되고있다.

주의할 것은 b(1+ (2*3)을 계산한 값)를 구하는 func함수의 인자 순서다.

1+(2*3)일 때, (2*3)+1가 아니라 1+(2*3)이다. 계산을 괄호식부터 할 뿐이다. 주의하자. 똑같은 얘기가 아니다.

즉, 순서를 주의해야한다.

예를들어 1-9-9일 때, func함수의 인자를 (sum,a)가 아닌 (a, sum)으로 바꾸면 1-(9-9)가 아닌 (9-9)-1가 되버려서 값이 달라져버린다.  

따라서, 인자는 sum뒤에 a가 나와야한다. (a뒤에 sum이 나오게되면안됨)

그리고, 잔실수 할수 있는 부분인데, func함수의 첫번째 인자는 num[cnt]이 아닌 sum이다.

1+(2*3)일 떄, 처음 계산할 때만 생각하면 sum=1이고 num[cnt]=1 이라 똑같은 값이라고 생각할 수 있는데, 그렇게되면 아래 식이 잘못된 값이 된다.

1+2*3+5*7일 떄를 보자.

만약 func의 첫번째 인자를 num[cnt]로 작성해버리면, 1+(2*3)=7까지 계산후 7+(5*7)이 아닌, 3+(5*7)이 된다. 즉, 누적된값을 유지해야한다.

위에서 길게 얘기한 것들을 코드로 작성하면된다.

코드

#include<iostream>
#include<string>
using namespace std;
int n;
string s;
int num[10],index1, index2, max_val = -100;
char op[10];
void dfs(int sum, int cnt);
int func(int a, int b, char c);
int main()
{
	cin.tie(0);
	cin.sync_with_stdio(false);
	cin >> n;
	cin >> s;
	for (int i = 0; i < s.size(); i++)
	{
		//숫자면 숫자배열에저장
		if (i % 2 == 0) {
			num[index1] = s[i] - '0';
			index1++;
		}
		else {
			op[index2] = s[i];
			index2++;
		}
	}
	dfs(num[0], 0);
	cout << max_val << '\n';
}
void dfs(int sum, int cnt)
{
	//모든 연산자를 사용하게됐을 때는 종료
	if (cnt == index2)
	{
		if (max_val < sum)
			max_val = sum;
		return;
	}
	//앞에서부터 계산하기
	int res = func(sum, num[cnt + 1],op[cnt]);
	//dfs돌려서 확인하기(더 계산할 수 있는지)
	dfs(res, cnt + 1);
	//괄호를 쳐서 계산하기
	//만약 계산할 연산자가 아직 남았으면 계산하기
	if (cnt + 1 < index2)
	{
		//1+2*3+5일 떄 1+(2*3)+5하는 과정
		int a = func(num[cnt + 1], num[cnt + 2], op[cnt + 1]);
		//조심!) func의 1,2번쨰 인자 순서바꾸면 틀림
		//조심!)func의 첫번째인자는 num[cnt]가 아님
		int b = func(sum, a, op[cnt]);
		//+5계산하기위해 2칸 건너뜀(+:0, *:1, +:2)
		dfs(b, cnt + 2);
	}
}
int func(int a, int b, char c)
{
	if (c == '+')return a + b;
	else if (c == '-')return a - b;
	else if (c == '*')return a * b;
	else
		exit(1);
}

결과