노는 게 제일 좋아

이것도 어렵다. 사실 BruteForce문제는 어렵다. 우리 머리 속에서 생략한 계산을 표현할 줄 알아야 하기 때문이다. 우리는 왜 숫자야구를 할 수 있을까? 왜 이것은 후보가 아닐까를..? 표현할 수 있어야 한다. 알아보자 https://www.acmicpc.net/problem/2503 #맞는 풀이 #include #include #include using namespace std; int N; // 주어진 힌트 수 bool num[1001]; int main(){ cin >> N; fill(num, num+1001, true); // 처음엔 숫자모르니까 다 정답의 후보 //하지만 같은 숫자가 있으면 후보가 될 수 없음. for (int i = 100; i n >> st >> b; string s =..

사실 이것은 정말 직관을 요하는 문제다. 브루트포스에 있지만.. 정말 브루트포스처럼 전수조사인지는 의문이다. https://www.acmicpc.net/problem/1120 #맞는 풀이 #include #include #include #include using namespace std; int main(){ string a; string b; cin >> a >> b; int lengthA = a.size(); int lengthB = b.size(); int numToAdd = lengthB-lengthA; int m = INT_MAX; // 최솟값 //lengthA에 대해서 lengthB의 어느 부분이랑 가장 매치가 되는지 //-> 가장 맞는 부분을 구한다면 해당 부분에서의 차이가 곧 전체의 차이임..

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; // 몇개나 다른 노..

할 말이 아주 많다. 어려웠다. 처음에 6가지 상태를 어떻게 표현하지.. 하다 차원이 무지막지하게 늘어나길래.. 이게 아닌가?? 하다가... 비트라는 힌트를 얻어서 풀었다. 잠잘 때도 어떻게 풀지 하다가.. 비트라는 힌트만 보고 머릿속으로 생각하고 오늘 바로 풀었다. 기분이 좋다. https://www.acmicpc.net/problem/1194 #맞는 풀이 #include #include #include #include #include //bit 연산을 위함 #define SIZE 50 using namespace std; int dx[4] = { -1,1,0,0 }; int dy[4] = { 0,0,-1,1 }; //key를 비트로 표현하자. 000000 -> 6비트로 표현가능 6가지 상태 저장가능 ..

1000* 1000의 탐색은 쉽게 시간초과가 된다는 것을 충분히 인지해야 한다. 그래서 어려웠다. 1000* 1000 사이즈의 노드에서 하나씩 BFS하는 것은 (1000 * 1000) 에 대해 (1000*1000) 을 수행하는 것과 같다. 즉, 시간초과다. https://www.acmicpc.net/problem/16946 #맞는 풀이 #include #include #include #include #include #define X first #define Y second #define SIZE 1000 using namespace std; int dx[4] = { -1,1,0,0 }; int dy[4] = { 0,0,-1,1 }; int r, c; //행, 열 char given[SIZE][SIZE];..

벽을 부수다가 기다릴 줄도 알아야한다는 것이 조금 까다롭다. https://www.acmicpc.net/problem/16933 #맞는 풀이 #include #include #include #define X first #define Y second #define SIZE 1000 using namespace std; int dx[4] = { -1,1,0,0 }; int dy[4] = { 0,0,-1,1 }; char arr[SIZE][SIZE]; //입력 int visited[SIZE][SIZE][11]; // 0 벽을 안깼다, 1 개깼다 .. 10개 깼다. int r, c, crush; typedef struct Position { int x; int y; int wall; int waiting; //..

벽을 여러개 부술 때이다. 1을 풀었다면 어떻게 해야할 지 알것이지만 벽만 바꾸는 것이 아니라 방문 조건도 바뀐다. 밑에서 조금 더 설명해보자 https://www.acmicpc.net/problem/14442 #맞는 풀이 #include #include #include #define X first #define Y second #define SIZE 1000 using namespace std; int dx[4] = { -1,1,0,0 }; int dy[4] = { 0,0,-1,1 }; char arr[SIZE][SIZE]; //입력 int visited[SIZE][SIZE][11]; // 0 벽을 안깼다, 1 개깼다 .. 10개 깼다. int r, c, crush; typedef struct Posi..

어려웠다. 개념이 아주 새로웠다. 복습 다시 천천히 해보자 https://www.acmicpc.net/problem/2206 #맞는 풀이 #include #include #include #define X first #define Y second #define SIZE 1000 using namespace std; int dx[4] = { -1,1,0,0 }; int dy[4] = { 0,0,-1,1 }; char arr[SIZE][SIZE]; //입력 int visited[SIZE][SIZE][2]; // 0 벽을 안깼다, 1 깼다 int r, c; typedef struct Position{ int x; int y; int wall; }Pos; int BFS(int _x, int _y) { queue ..

음 백트래킹하면서 DFS로 끝까지 가는 것이라 처음 접했을 때는 어려웠다. https://www.acmicpc.net/problem/1987 #맞는 풀이 ( 백트래킹 + DFS ) #include #include #include #include using namespace std; int dx[4] = {-1,1,0,0}; int dy[4] = {0,0,-1,1}; char arr[20][20]; int alpha[26]; // ASCII 코드 이용하기 'A' = 65 'a'=97 int R,C; //Row(행) , Column(열) int answer = 0; // 최댓값 //현재 위치, 현재까지의 길이 void dfs(int x, int y, int dist){ // 최댓값 갱신 answer = ma..

음.. 생각은 빨리했는데.. 오래걸림.. 왜냐면.. 초기화를 잘못했다. 아...내 1시간반 https://www.acmicpc.net/problem/14502 그렇게 어렵지 않았다. 벽을 무작위로 세워야 하는 것을 이미 알기에.. Brute Force를 해야하는 것은 알았지만 그냥 백트래킹 복습삼아 적용했다. 가장 처음 제출한 풀이.. #include #include #include #define X first #define Y second using namespace std; int map[8][8]; int visited[8][8]; int dx[4] = {1,-1,0,0}; int dy[4] = {0,0,1,-1}; int N,M; int ans = 64; stack stk; // DFS 스택 ve..