백준 문제 해설66 백준 7595 Triangles 큐빙 맞왜틀.. 이건 말이 안된다 반례를 찾았는데도 모르겠다. https://www.acmicpc.net/problem/7595 7595번: Triangles Each line of input contains a single positive integer, n, 1 n){ if(n==0) break; FOR(i,0,n){ FOR(j,0,i+1) cout 2022. 11. 24. 백준 17267 상남자 0-1 bfs 응용문제? https://www.acmicpc.net/problem/17267 17267번: 상남자 CTP의 대표 상남자 영조는 자유롭게 이동하는 것을 좋아한다. 그렇지만 영조는 상남자이기 때문에 위아래로만 간다. 따라서 위, 아래로는 얼마든지 이동할 수 있지만 왼쪽, 오른쪽으로는 이동하 www.acmicpc.net 풀이 그래프를 탐색하며 상하로 이동하는 것의 비용은 0이고 좌우로 이동하는 것의 비용은 1이다. 단순 bfs에 push_front 를 추가한다고 생각하면 된다. 비용이 0인 이동을 push_front로 이동해 도달할 수 있는 모든 곳을 도달해야한다. 백준 게시판에서 반례를 찾아보고 해결하였다. 상하좌우로 한칸씩 이동할 경우 다음의 케이스에서 (2,3) 지점을 탐색해줄 수 없다... 2022. 11. 23. 백준 16234 인구 이동 플레 5 풀다가 너무 무서워져서 골드 5로 내려왔다. 편안. https://www.acmicpc.net/problem/16234 16234번: 인구 이동 N×N크기의 땅이 있고, 땅은 1×1개의 칸으로 나누어져 있다. 각각의 땅에는 나라가 하나씩 존재하며, r행 c열에 있는 나라에는 A[r][c]명이 살고 있다. 인접한 나라 사이에는 국경선이 존재한다. 모 www.acmicpc.net 풀이 매번 연결해주고 연결 정보를 vector v로 관리해주고 초기화해주고 하며 교환이 발생하지 않을 때까지 이를 반복해준다. 시간 복잡도 : $O(2000*N^2)$ 감상 : 처음에 많이 해맸다. 일찍이부터 그냥 bfs 써서 했으면 편하게 했을걸 괜히 엄한 방법으로 하려다 시간만 많이 썼다. 아쉽다. /* basic se.. 2022. 11. 22. 백준 25386 라즈베리 파이 플레 2가 푸는 플레 2 문제.. 뭐가 안 맞습니다. https://www.acmicpc.net/problem/25386 25386번: 라즈베리 파이 한별이는 $3$년 만에 오프라인으로 개최되는 UCPC 본선을 맞아 특별한 이벤트를 계획했다. 바로 참가자들과 라즈베리 파이를 나눠 먹는 것이다! 한별이는 원기둥 모양의 파이를 모든 조각이 밑면 www.acmicpc.net 풀이 라즈베리(토핑)을 최소로 이동해주는 방법을 생각하기 이전에 모든 참가자의 요구를 들어줄 수 없는 경우(-1)를 먼저 생각해야 한다. 토핑은 한 번 합쳐지면 다시 나누어질 수 없기 때문에 모든 참가자들의 요구를 들어줄 수 없는 경우가 발생한다. 모든 참가자의 요구를 들어줄 수 없는 경우는 다음 세 가지로 나뉜다. 1. 서로 다른 두 참.. 2022. 11. 21. 백준 4354 문자열 제곱 오랜만에 플래티넘 문제 풀었다. 기분 좋다. https://www.acmicpc.net/problem/4354 4354번: 문자열 제곱 알파벳 소문자로 이루어진 두 문자열 a와 b가 주어졌을 때, a*b는 두 문자열을 이어붙이는 것을 뜻한다. 예를 들어, a="abc", b="def"일 때, a*b="abcdef"이다. 이러한 이어 붙이는 것을 곱셈으로 생각한다 www.acmicpc.net 풀이 실패 함수를 활용해줘야 한다. 실패 함수를 통해 문자열이 얼마나 겹치는지 $O({s1.size()})$동안 확인해줄 수 있다. 이를 바탕으로 sz(s1)/(sz(s1)-pr) 해당 식을 통해 최대 n을 구해줄 수 있는 것이다. 50%에서 틀렸습니다가 계속 나오는 경우 소수인 펠린드롬을 고려해줬는지 다시 한번 생각.. 2022. 11. 20. 이전 1 2 3 4 5 ··· 14 다음
