빅맥좋아요

https://www.acmicpc.net/problem/1932 1932번: 정수 삼각형 첫째 줄에 삼각형의 크기 n(1 ≤ n ≤ 500)이 주어지고, 둘째 줄부터 n+1번째 줄까지 정수 삼각형이 주어진다. www.acmicpc.net 백준 1932번 정수 삼각형을 풀어봤습니다. 삼각형의 가로줄에서 양 끝에 있는 경우와 꼭대기에 있는 경우만 주의해서 조건을 걸어주면 됩니다. 아래는 전체 코드입니다. #include #include using namespace std; int triangle[500][500]; int cost[500][500]; int dp(int n, int k) { if (cost[n][k] != -1) return cost[n][k]; if (n == 0) { cost[0][0]..

https://www.acmicpc.net/problem/1149 1149번: RGB거리 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 www.acmicpc.net 백준 1149번 RGB거리를 풀어봤습니다. 최적해를 구해야 하는데 매 순간 최적해를 구하는 그리디 방법이 아니라 모든 경우를 찾는 동적계획법을 사용했습니다. 마지막 집이 빨강, 초록, 파랑으로 칠해지는 3가지 경우에 대해 dp함수에 넣고, 결과값을 비교해서 최솟값을 출력하면 됩니다. dp함수에서 이미 계산했던 적이 있는 경우라면 바로 반환합니다. n==0인 상태에선 입력으로 ..

https://www.acmicpc.net/problem/5430 5430번: AC 각 테스트 케이스에 대해서, 입력으로 주어진 정수 배열에 함수를 수행한 결과를 출력한다. 만약, 에러가 발생한 경우에는 error를 출력한다. www.acmicpc.net 백준 5430번 AC를 풀어봤습니다. 자료구조 deque를 사용해서 배열을 뒤집는 연산을 하지 않고 pop_back()과 pop_front()로 R연산을 해줬습니다. 아래는 전체 코드입니다. #include #include #include #include using namespace std; deque dq; string ans[100]; bool funtion(string work, deque& dq, bool *isReverse) { for (int..

https://www.acmicpc.net/problem/1504 1504번: 특정한 최단 경로 첫째 줄에 정점의 개수 N과 간선의 개수 E가 주어진다. (2 ≤ N ≤ 800, 0 ≤ E ≤ 200,000) 둘째 줄부터 E개의 줄에 걸쳐서 세 개의 정수 a, b, c가 주어지는데, a번 정점에서 b번 정점까지 양방향 길이 존 www.acmicpc.net 백준 1504번 특정한 최단경로를 풀었습니다. 시작 정점에서 마지막 정점까지 v1, v2 정점을 반드시 지나야 합니다. 최단 경로의 경우의 수는 start -> v1 -> v2 -> end 와 start -> v2 -> v1 -> end 로 두가지입니다. 따라서 start정점, end정점, v1정점에 대하여 다익스트라 함수를 총 3번 사용해야합니다. 그..

https://www.acmicpc.net/problem/2580 2580번: 스도쿠 스도쿠는 18세기 스위스 수학자가 만든 '라틴 사각형'이랑 퍼즐에서 유래한 것으로 현재 많은 인기를 누리고 있다. 이 게임은 아래 그림과 같이 가로, 세로 각각 9개씩 총 81개의 작은 칸으로 이루 www.acmicpc.net 백준 2580번 스도쿠를 풀어봤습니다. 비어있는 곳을 벡터에 넣어서 백트래킹 함수에서 사용했습니다. isPromising함수에서 같은 열, 같은 행, 같은 구역인지 체크하고 promising하면 true를 넘겨줬습니다. 아래는 전체 코드입니다. #include #include #include #include using namespace std; int board[9][9]; vector v; bo..

https://www.acmicpc.net/problem/9663 9663번: N-Queen N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오. www.acmicpc.net 백준 9663번 N-Queen문제를 풀어봤습니다. 처음엔 2차원 배열로 체스판을 만들어서 풀면 쉬울 것 같아서 2차원 배열로 풀었더니 시간 초과가 나왔습니다. 그래서 1차원 배열로 바꾸고 배열의 인덱스를 y좌표, 배열의 값을 x좌표로 가정하고 풀었습니다. board[1]=2 면 (1,2)에 퀸이 위치한 것입니다. 입력받은 n만큼 순회하면서 해당 level(y좌표)과 i(x좌표)에 퀸을 놓습니다. 그 다음 퀸을 놓..

https://www.acmicpc.net/problem/1753 1753번: 최단경로 첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1 ≤ V ≤ 20,000, 1 ≤ E ≤ 300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 K(1 ≤ K ≤ V)가 www.acmicpc.net 백준 1753번 최단 경로를 풀어봤습니다. 우선순위 큐에서 두 번째 인자에 가중치를 넣었고 가중치를 오름차순으로 정렬하기 위해 compare 구조체를 정의했습니다. 인접리스트로 풀었고 큐에 시작점과 가중치 0을 넣고 다익스트라 함수에 넣었습니다. 그 후엔 다익스트라 함수에서 시작점과 인접한 정점부터 탐색을 시작합니다. BFS와 비슷한 구조인데 가중치만 추가된 ..

https://www.acmicpc.net/problem/1107 1107번: 리모컨 첫째 줄에 수빈이가 이동하려고 하는 채널 N (0 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 고장난 버튼의 개수 M (0 ≤ M ≤ 10)이 주어진다. 고장난 버튼이 있는 경우에는 셋째 줄에는 고장난 버튼 www.acmicpc.net 백준 1107번 리모컨문제를 풀어봤습니다. 직관적으로 풀려다가 6중 for문을 사용하게 됐습니다. 버튼 0이 고장났을 때 자릿수에 맞춰서 if문을 적용시켜줘야 합니다. 반복문에서 222는 000222므로 앞에 있는 세자리의 0은 무시하고 계산했습니다. 아래는 전체 코드입니다. #include #include #include #include #include using namespac..

https://www.acmicpc.net/problem/7562 7562번: 나이트의 이동 체스판 위에 한 나이트가 놓여져 있다. 나이트가 한 번에 이동할 수 있는 칸은 아래 그림에 나와있다. 나이트가 이동하려고 하는 칸이 주어진다. 나이트는 몇 번 움직이면 이 칸으로 이동할 수 www.acmicpc.net 백준 7562번 나이트의 이동을 풀어봤습니다. 간단한 BFS문제 입니다. 테스트 케이스마다 큐와 배열을 초기화해줘야 합니다. 아래는 전체 코드입니다. #include #include #include #include #include using namespace std; int t, l; int dx[8] = { 1,2,2,1,-1,-2,-2,-1 }; int dy[8] = { 2,1,-1,-2,-2,..

https://www.acmicpc.net/problem/1707 1707번: 이분 그래프 입력은 여러 개의 테스트 케이스로 구성되어 있는데, 첫째 줄에 테스트 케이스의 개수 K가 주어진다. 각 테스트 케이스의 첫째 줄에는 그래프의 정점의 개수 V와 간선의 개수 E가 빈 칸을 사이에 www.acmicpc.net 백준 1707번 이분 그래프를 풀어봤습니다. graph의 첫 좌표는 본인입니다. 예를 들어 graph[2][0]은 (2,0)으로, graph[3][0]은 (3,0)으로 초기화 됩니다. 그 다음엔 인풋이 양방향 간선이라 하나는 정방향, 하나는 역방향으로 총 두번 넣었습니다. 테스트 케이스별로 꼭 큐와 배열들을 초기화 해줘야 합니다. 맞았는데 왜 틀렸는지 찾는 경우가 사라집니다. BFS함수의 for문..