https://www.acmicpc.net/problem/3049 3049번: 다각형의 대각선 세 대각선이 한 점에서 만나지 않는 볼록 N각형이 주어졌을 때, 대각선의 교차점의 개수를 세는 프로그램을 작성하시오. 아래 그림은 위의 조건을 만족하는 한 육각형의 교차점 그림이다. 모든 www.acmicpc.net 수학문제. "세 대각선이 한 점에서 만나지 않는" 이라는 조건이 중요하다. 근데 아마 지문이슈가 좀 있는거같은게 N>=3 인 N개의 대각선이 한점에서 만나지 않는 이 좀 더 정확하지 않나 싶다. 암튼 세 대각선이 한 점에서 겹치지 않는다면 대각선의 교차점이 생기는 경우는 무조건 두 대각선이 서로 한 점에서 만나는 경우인데, 대각선은 볼록 N각형의 꼭짓점에서 임의의 점 두개를 골라서 만들어 낼 수 있..

범위가 터무니없어서 의심이 갔던 문제. https://www.acmicpc.net/problem/9660 9660번: 돌 게임 6 첫째 줄에 N이 주어진다. (1 ≤ N ≤ 1,000,000,000,000) www.acmicpc.net 풀고나서 확인해보니 돌 게임3의 확장버전이라고 한다 돌 게임 3도 풀고 와야지 히히 범위가 하도 터무니 없다는 점에서 무언가 꼼수가 있겠다 싶어 일단 100개 정도만 dp를 통해서 구해보았다. dp를 통해 구한 방법은 dp[k-1], dp[k-3], dp[k-4] 중에 창영이가 반드시 승리하는 경우가 있다면 상근이의 승리, 아니라면 창영이의 승리에 해당한다. 중요한것은 아니니 짧게 적어보고 암튼 해당 방법을 통해서 구해놓고 보니 알수 있었던 점으로 1111 네개가 붙어있는..

변수초기화를생활화하자! 변수초기화를생활화하자! 변수초기화를생활화하자! ㅠㅠㅠㅠ https://www.acmicpc.net/problem/12869 12869번: 뮤탈리스크 1, 3, 2 순서대로 공격을 하면, 남은 체력은 (12-9, 10-1, 4-3) = (3, 9, 1)이다. 2, 1, 3 순서대로 공격을 하면, 남은 체력은 (0, 0, 0)이다. www.acmicpc.net 수의 범위가 크지 않아서 DP배열을 선언하기 그리 어렵지 않다. DP배열을 선언해두고 dfs나 bfs 등의 방법으로 가능한 가짓수 여섯가지 경우에 대해 탐색을 해주면 되는데, 탐색 중간에 SCV의 체력이 음수로 내려가는경우 음수 인덱스에 접근하게 되면서 세그폴트가 발생할 수 있으므로, k = max(k,0) 등의 구문을 통해서 ..

숫자범위 자비좀.... https://www.acmicpc.net/problem/2870 2870번: 수학숙제 종이에서 찾은 숫자의 개수를 M이라고 하면, 출력은 M줄로 이루어져야 한다. 각 줄에는 종이에서 찾은 숫자를 하나씩 출력해야 한다. 이때, 비내림차순으로 출력해야 한다. 비내림차순은 내림차 www.acmicpc.net 일단 문제 지문에서 유추해내야 하는 조건으로써 나오는 숫자의 길이가 매우 길어져서 int 및 long long 으로 저장할 수 없는 경우가 있다. 따라서 숫자를 다룰생각을하지를 말고 문자열로 다뤄줘야 하는 문제. 문자열을 가지고 놀기 위해서 몇몇가지 함수를 짜줬다. 1. bool isalpha(char c) 들어온 글자 한글자가 영문자인지 체크하는 함수. bool isalpha(c..

소수이면서 팰린드롬인 수를 구하는 문제. 문제에서 요구하는대로 소수인 수들을 미리 구해놓고, 이들 중에서 팰린드롬인 수를 찾으면 된다. https://www.acmicpc.net/problem/1747 1747번: 소수&팰린드롬 어떤 수와 그 수의 숫자 순서를 뒤집은 수가 일치하는 수를 팰린드롬이라 부른다. 예를 들어 79,197과 324,423 등이 팰린드롬 수이다. 어떤 수 N (1 ≤ N ≤ 1,000,000)이 주어졌을 때, N보다 크거나 같고, www.acmicpc.net 소수의 판정은 에라스토테네스의 체 방법을 활용했다. sleve[0] = 1; sleve[1] = 1; for(int i=2; i

https://www.acmicpc.net/problem/17615 17615번: 볼 모으기 첫 번째 줄에는 볼의 총 개수 N이 주어진다. (1 ≤ N ≤ 500,000) 다음 줄에는 볼의 색깔을 나타내는 문자 R(빨간색 볼) 또는 B(파란색 볼)가 공백 없이 주어진다. 문자열에는 R 또는 B 중 한 종류만 주 www.acmicpc.net R이랑 B 두가지 색을 가진 공을 적절하게 이동시켜서 같은색끼리 모으는 문제이다. 처음 보고 들었던 생각은 R에 0 B에 1 이런느낌으로 숫자할당을 해서 swap 정렬횟수를 세는 inversion counting 유형인줄 알았다. 하지만 인접한 두 원소간의 교환이 아니라서 해당 가설(?) 은 부정됨. 두번째로 생각했던 것은 에서처럼 R이 뭉쳐져 있는 쪽으로 남은 R을 ..