TIL day 76

1. 코딩테스트

---

class 5의 용액 문제를 풀었습니다.

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

#include <iostream>
#include <climits>
using namespace std;

int n;
int board[100'002];
int answer = INT_MAX;
pair<int, int>ans;

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	cin >> n;
	
	fill(board, board + 100002, INT_MAX);

	for (int i = 0; i < n; ++i)
	{
		cin >> board[i];
	}
	
	int st = 0;
	int en = n - 1;

	while (st < en)
	{
		int sum = board[st] + board[en];
		if (answer > abs(sum))
		{
			answer = abs(sum);
			ans = make_pair(board[st], board[en]);
		}
		//음수
		if (sum < 0)
			st++;
		else
			en--;
	}

	cout << ans.first << " " << ans.second;
	
}

• 처음에 문제를 보고 바로 투포인터라고 생각은 들었는데, 투포인터를 오랜만에 접하다보니 쉽게 풀지는 못했습니다.
• 투포인터쪽도 좀 더 템플릿을 만들어서 문제를 풀어봐야할 것 같다는 생각이 들었습니다.
• 생각의 흐름
  • st와 en을 둘 다 왼쪽에서 시작해서, 다음 값이 더 커진 경우 st를 증가시키고 아닌 경우는 en을 증가하는 식으로 구현했는데 예외가 생기는지 쉽게 풀리지 않았습니다.
  • 그래서 st와 en을 양 끝으로 두고, 다가오는 방향으로 생각해 보았고, 합이 음수가 되는 것을 기준으로 해결하였습니다.

class 4 의 거짓말 문제를 풀었습니다.

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

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

int n, m;
int t;
int tarr[52];
vector<int> Data[52];
vector<int> adj[52];
int vis[52];
int answer = 0;

void bfs(int cur)
{
	queue<int>q;
	q.push(cur);
	vis[cur] = 1;

	while (!q.empty())
	{
		int cur = q.front();
		q.pop();

		for (int nxt : adj[cur])
		{
			if (!vis[nxt])
			{
				vis[nxt] = 1;
				q.push(nxt);
			}
		}
	}
}
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	//사람, 파티
	cin >> n >> m;
	//진실
	cin >> t;
	for (int i = 0; i < t; ++i)
	{
		cin >> tarr[i];
	}
	
	for (int i = 0; i < m; ++i)
	{
		int p;
		cin >> p;
		for (int j = 0; j < p; ++j)
		{
			int num;
			cin >> num;
			Data[i].push_back(num);			
		}
		for (int j = 0; j < Data[i].size() - 1; ++j)
		{
			adj[Data[i][j]].push_back(Data[i][j + 1]);
			adj[Data[i][j + 1]].push_back(Data[i][j]);
		}
	}

	for (const auto& ta : tarr)
	{
		bfs(ta);
	}

	for (int i = 0; i < m; ++i)
	{
		bool fun = true;
		for(int j = 0 ; j < Data[i].size();++j)
		{
			if (vis[Data[i][j]])
			{
				fun = false;
				break;
			}
		}
		if (fun)
			answer++;
	}
	cout << answer;
}

• 처음 보고, 그래프 구성해서 연관된 것들을 체크 후 (bfs) 다시 모든 경우의 수를 돌면서 해당하는 경우의 수를 더해주면 될 것이라는 생각을 했습니다.
• 생각의 흐름
  • Data라는 답을 내기 위해서 입력받은 값들을 넣은 벡터를 구성합니다.
  • 이후로 adj라는 인접리스트 형식의 그래프를 구성하고, 진실을 아는 사람들을 하나씩 시작점으로 선택하여 bfs를 돌리면 그 결과 진실을 알게된 사람들이 체크가 됩니다.
  • 마지막으로 Data 를 돌면서 방문한 경우(vis가 true면, 진실을 아는 사람) 를 제외하고 answer를 더해주어 답을구했습니다.
• 좀 더 깔끔하게 풀 수 있을것 같기도 한데, 일단 생각의 흐름을 따라서 코드를 작성하니 조금 복잡하게 된 것 같기도 합니다.

 

 

2. 언리얼

---