노는 게 제일 좋아

DFS + DP 문제다. 나는.. DP를 까먹고 있어서 답을 결국 봐버렸다.ㅠㅠ 어쩐지.. 이 문제는 중요해보였다. 아니 우선 나에게 통찰력을 주었다. https://www.acmicpc.net/submit/12869/48753292 #맞은 풀이 #include using namespace std; //재귀만 해보려는데 도저히 생각이 안나서...답을 찾았다. int dp[61][61][61]; //DP를 사용하라는데.. 재귀 + DP란다. //scv 체력 a,b,c에 대해서 각 공격을 적용해본다. int func(int a, int b, int c){ //죽은 scv에 대해서는 연산하지 않는다. //이 처리를 하는 이유는 음수에 대한 계산을 하지 않기 때문이다. if(a> N; //배열 모두 초기화 me..

이것도 재밌고 문제로 나오지 않을까? 싶다. https://www.acmicpc.net/problem/2146 #맞은 풀이 #include using namespace std; #define X first #define Y second int dx[4] = {1,-1,0,0}; int dy[4] = {0,0,1,-1}; int N; int conti[100][100]; int area[100][100]; int dist[100][100]; int flag = 1; int minDist = INT_MAX; void DFS(int x, int y){ area[x][y] = flag; for(int dir = 0; dir= N || ny = N)continue; if(area[nx][ny]..

이 문제도 구현 중 엄청 어려운 편에 속한다. 우선 나는 그렇다. 이건 진짜 어려웠다. 아니 알파고는 어떻게 계산함? https://www.acmicpc.net/problem/16571 #맞은 풀이 #include using namespace std; //게임은 누가먼저 시작하느냐에 따라 달라짐. string answer; //게임이 끝났는지(turn이 이기거나 지거나) 체크 //turn은 O 또는 X임 bool CheckGameEnd(vector& board, char turn){ //가로로 이겼는지 for(int i = 0; i

난 아주 고난이도라고 생각하는 구현 문제다. 해당 게임을 해봤음에도.. 나는 이 문제를 푸는데 오랜 시간이 걸렸다. https://www.acmicpc.net/problem/12100 #맞은 풀이 #include using namespace std; int maxNumber = -1; int N; // N*N size vector vec; void DFS(int cnt, vector& board); void shiftBlock(int type, vector& board); //1 => 모든 경우를 살펴봐야함. int solution(vector& board) { DFS(0, board); return maxNumber; } //2 void DFS(int cnt, vector& board){ //모든 경우..

//첫번째 풀이 2021.06.07 //두번째 풀이 2022.02.08 //세번째 풀이 2022.06.13 얘도 모든 걸 다 뒤져봐야 하는 문제다. 다만 모든 걸 뒤질 때 어떻게 뒤지느냐가 문제다. 백트래킹, DFS를 사용했다고 보면 된다. https://www.acmicpc.net/submit/14888/29858716 #맞는 풀이 #include #include #define MAX 1000000000 using namespace std; int N; int num[12]; int oper[4]; // {add, sub, mul, div 순} //최대 최소 int m = MAX; int M = -MAX; //백트래킹 이용같다. //입력은 현재까지의 연산결과를 받고 사용한 연산자 개수도 입력받는다 vo..

어렵지 않았다. 다만 머리로 아 어떡하지? 중복제거 어떡하지?? set 생각날 때까지 어려웠다. https://www.acmicpc.net/problem/5568 #맞은 풀이 #include using namespace std; int n,k; set numbers; vector card; bool check[10]; //카드를 고르면서 정수를 만듬. void func(int cnt, string s){ if(cnt == k){ numbers.insert(stoi(s)); //1,3 과 13은 자리를 바꿔도 같은 정수라 중복 제거해야함. //set 이용 return; } for(int i=0; i> n >> k; for(int i=0; i> x; card.push_back(x); } func(0,"");..

시간초과가 왜 난지 몰랐지만.. 그냥 나중에 생각해보니 날만했었다. https://www.acmicpc.net/problem/1062 #맞은 풀이 #include #include #include #include using namespace std; bool alpha[26]; int N, K; vector vec; int ans = 0; //idx를 추가시켜서 시간을 단축 시켰다. //여기서 idx는 for문이 시작하는 번호를 말한다. void func(int cnt, int idx) { //K-5개만큼 골랐다면 if (cnt == K-5) { int cnt = 0; //각 단어를 읽을 수 있는지 조사 for (string str : vec){ bool read = true; //만약 모르는 글자가 나오..

사실 어렵다기보다는 생각이 어렵다. 구현은 어렵지 않다. 솔직히 힌트를 얻어서 했지만.. 과연 내가 혼자서 할 수 있을까?? 는 고민이다. https://www.acmicpc.net/problem/2842 #맞은 풀이 #include #include #include //distance를 쓰기 위함 #include using namespace std; const int MAX = 51; const int INF = 987654321; char pos[MAX][MAX]; int height[MAX][MAX]; int visited[MAX][MAX]; int dr[8] = { -1,-1,-1,0,0,1,1,1 }; int dc[8] = { -1,0,1,-1,1,-1,0,1 }; set h; int N; int..

사실 처음 들었을 때 이분그래프의 정의가 알아듣기 힘들었다. 그래프의 정점의 집합을 둘로 분할하여, 각 집합에 속한 정점끼리는 서로 인접하지 않도록 분할할 수 있을 때, 그러한 그래프를 특별히 이분 그래프 (Bipartite Graph) 라 부른다. ??음.. 무슨 말이지?? 즉, 나는 내 집합의 정점과 연결되면 안된다...? 그렇다. 그냥 색을 2가지로 칠할 수 있을 때 인접한 노드가 나와 같은 색을 가지면 안된다는 말과 같다. https://www.acmicpc.net/problem/1707 #맞은 풀이 #include #include #define X first #define Y second #define MAX 20001 using namespace std; int K; // 테스트케이스 수 in..

DFS + DP 문제다. DFS를 어떻게 설계해야할까? 가 문제다. https://www.acmicpc.net/problem/1937 #맞는 풀이 #include #include #define X first #define Y second using namespace std; int dx[4] = { -1,1,0,0 }; int dy[4] = { 0,0,-1,1 }; int map[500][500]; int dp[500][500]; int N; int ans; //좌표 int dfs(int x, int y) { //만약 저장되어있지 않으면 if(dp[x][y] == 0){ dp[x][y] = 1; // 우선 해당 노드에서 1일 살 수 있음( + 방문체크와 같음) int cnt = 0; // 몇개나 다른 노..