맛있는감귤

문제 : https://www.acmicpc.net/problem/2206 github : https://github.com/JEONG-SEUNGWOOK/BOJ/blob/master/2206.cpp BFS를 이용한 미로찾기에서 벽을 부수는 스킬이 추가되었다. 종종 벽을 부순다거나 폭탄이 주어진다거나 하는 문제 유형이 있는데 그 중의 기본 문제이다. 내 해결 방법은 방문체크(isVisited)배열을 한 차원 더 늘려 벽을 부쉈을 때, 안 부쉈을 때를 나눠 탐색했다. 더 좋은 해결 방법이 있으면 댓글 남겨주시면 감사하겠습니다. #include #include using namespace std; struct Pos{ int x,y,bomb; }; int N,M,dis=1,ans=0; char map[1001..

문제 : https://www.acmicpc.net/problem/2178 github : https://github.com/JEONG-SEUNGWOOK/BOJ/blob/master/2178.cpp 지극히 기본적인 BFS 문제 #include #include using namespace std; int N,M,ans=1; queue q; char map[102][102]; bool isVisited[102][102]; int px[4]={1,-1,0,0}; int py[4]={0,0,1,-1}; int main(){ cin>>N>>M; for(int i=0; i>map[i]; pair s; s.first=0, s.second=0; isVisited[s.first][s.second]=true; q.push..

문제 : https://www.acmicpc.net/problem/1966github : https://github.com/JEONG-SEUNGWOOK/BOJ/blob/master/1966.cpp출처ACM-ICPC > Regionals > Europe > Northwestern European Regional Contest > NWERC 2006 F번ACM-ICPC Live ArchivePKU Judge OnlineTJU Online JudgeSphere Online JudgeHDU Online Judge 입력값이 작아 부르트 포스로 풀 수 있을 것 같지만 디큐를 이용해서 풀어보았다. #include #include using namespace std; int main(){ int T; cin>>T; w..

문제 : https://www.acmicpc.net/problem/1965 DP(다이나믹 프로그래밍)으로 해결가능하다. 이런 문제를 최장 증가 수열 (LIS, Longest Increasing Subsequence) 이라고도 한다. 웬만한 크기가 작은 LIS문제는 아래의 코드로 다 해결이 가능하다LIS O(N^2)의 시간복잡도의 코드 for(int i=0;i

문제 : https://www.acmicpc.net/problem/1932 출처 Olympiad > International Olympiad in Informatics > IOI 1994 1번PKU Judge OnlineSphere Online JudgeDP(다이나믹 프로그래밍)로 해결했다. 삼각형 꼭대기 값을 아래 행에 더해주며 최대값을 저장해 마지막에 출력한다. #include #include using namespace std; int N ,max_sum=0;; int num[505][505]; int sum[505][505]={0,}; int main(){ scanf("%d",&N); scanf("%d",&num[0][0]); sum[0][0] = num[0][0]; max_sum = 0; for..

문제 : https://www.acmicpc.net/problem/1924 기준 날짜부터 주어진 날짜까지 일 수를 다 더한후 7의 나머지 값에 따라 요일 출력 #include int main() { int a, b; int cal[13] = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31}; scanf("%d %d",&a, &b); int day=0; for(int i=0; i

문제 : https://www.acmicpc.net/problem/1922최소 스패닝 트리 문제이다.프림 알고리즘으로 해결 #include #define INF 1000000001 int N, M; int com[1002][1002]; int dist[1002]; int isVisited[1002]; int sum=0; void input(){ scanf("%d %d",&N, &M); for(int i=1;i

문제 : https://www.acmicpc.net/problem/1916 일반적인 다익스트라 알고리즘 구현 문제 #include #define INF 987654321; int V, E; int start,end; int map[1002][1002]; int dist[1002]; int isVisited[1002]; void input(){ scanf("%d %d", &V, &E); for(int i=1; i

문제 : https://www.acmicpc.net/problem/11945 출처 University > 고려대학교 > 2016 고려대학교 신입생 프로그래밍 경시대회 D번입력된 숫자를 뒤집어서 출력하는 문제 #include #include using namespace std; int main(){ int N,M; string s; cin>>N>>M; while(N--){ cin>>s; for(int i=0;i

문제 : https://www.acmicpc.net/problem/6378출처 ACM-ICPC > Regionals > North America > Greater New York Region > 2000 Greater New York Programming Contest C번ACM-ICPC Live ArchivePKU Judge OnlineZJU Online JudgeTJU Online JudgeHDU Online Judge입력 N의 각 자리수의 값을 더해 나온 값이 한 자리 숫자가 될 때까지 반복하는 문제이다.문제의 핵심은 '수는 최대 1000자리이다.' 이 부분이다.최대 1000으로 봤는데 자세히 보니 1000'자리'이다. 그래서 string으로 해결. #include #include using nam..